home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / sos3-2.lha / src / agg / Mapping.c < prev    next >
C/C++ Source or Header  |  1992-01-23  |  116KB  |  2,769 lines
  1. /* --------------------------------------------------------------------------
  2.  * Copyright 1992 by Forschungszentrum Informatik (FZI)
  3.  *
  4.  * You can use and distribute this software under the terms of the licence
  5.  * you should have received along with this program.
  6.  * If not or if you want additional information, write to
  7.  * Forschungszentrum Informatik, "STONE", Haid-und-Neu-Strasse 10-14,
  8.  * D-7500 Karlsruhe 1, Germany.
  9.  * --------------------------------------------------------------------------
  10.  */
  11. // **************************************************************************
  12. // Module Mapping                   9/8/90                    Jochen Alt (ja)
  13. //                                                   modified : 24/10/91 (bs)
  14. //                                                   modified : 22/11/91 (ja)
  15. // **************************************************************************
  16. // implements methods of classes: Mapping, sos_Map_node
  17. // **************************************************************************
  18.  
  19. #include "agg_err.h"
  20. #include "trc_agg.h"
  21. #include "sys.h"
  22. #include "Mapping.h"
  23. #include "agg_sos.h"
  24.  
  25. // erweiterbares Hash-Verfahren mit leichten Modifikationen
  26. // Quelle : Datenbankhandbuch Seite 247
  27. // siehe externe Dokumentation
  28.  
  29. #define get_key_based_on_equal()  get_role1_based_on_equal()
  30. #define get_info_based_on_equal() get_role2_based_on_equal()
  31. #define set_key_based_on_equal(b)  set_role1_based_on_equal(b)
  32. #define set_info_based_on_equal(b) set_role2_based_on_equal(b)
  33.  
  34. inline int absolute(int d) { return (d>0)?d:-d; }
  35.  
  36. const sos_Offset NIL=0;
  37.  
  38. // Da psm direkt benutzt wird, wird ein Datentyp  benoetigt, der
  39. // anstelle der Objekte abgespeichert wird. Dies ist ein object_save_t,
  40. // der augenblicklich als sos_Typed_id definiert ist. Die beiden Operatoren,
  41. // die object_save_t in sos_Object und umgekehrt konvertieren, sind
  42. // make_object_save und make_Object
  43. // ************************************************************************** 
  44. object_save_t make_object_save (sos_Object o)
  45. // ************************************************************************** 
  46. // nimm das sos_Object o, bastle daraus ein object_save, und
  47. // liefere es in os zurueck
  48. {  sos_Typed_id  tpid = o.typed_id();
  49.    object_save_t os;
  50.    bcopy_from_sos_Typed_id(&tpid,&os);
  51.    return os;
  52. } 
  53.  
  54. // ************************************************************************** 
  55. sos_Object make_Object (object_save_t &os)
  56. // ************************************************************************** 
  57. // nimm den object_save os, mache daraus ein sos_Object und liefere es zurueck
  58. {  sos_Typed_id tpid;
  59.    bcopy_to_sos_Typed_id(&tpid,&os);
  60.    return sos_Object::make(tpid);
  61. } 
  62.  
  63. /*
  64. Abhaengig von sos_Bool:list_cursor gibt es zwei Versionen eines Mappings:
  65. 1. Version: list_cursor = FALSE
  66.    Die Cursoroperatoren sind nur auf einem statischen Mapping
  67.    definiert. Wird ein Objekt eingefuegt, so kan sich die Cursor-Reihenfolge
  68.    voellig veraendern. Damit ist ein sinnvoller Umgang mit Cursorn nur auf
  69.    einem sich nicht veraendernden Mapping moeglich. Sobald etwas eingefuegt 
  70.    oder geloescht wird, sind die Cursor zu schliessen und neu von vorne 
  71.    zu beginnen. Die Reihenfolge der Objekte ist durch die
  72.    Reihenfolge in der Hashtabelle definiert, also fuer den Benutzer rein
  73.    zufaellig. In dieser Version braucht ein Eintrag 36 Byte (= 2x sos_Object
  74.    und ein Hashwert a 4 byte)
  75. 2. Version : list_cursor = TRUE
  76.    Die Cursor-Operatoren koennen auch an einem dynamischen Mapping gleich-
  77.    zeitig ausgefuehrt werden. Die einzelnen Eintraege sind miteinander
  78.    doppelt verkettet, ein Einfuegen erfolgt am Anfang der Liste. Ein Eintrag
  79.    braucht damit 36+2x16 = 68 Byte (zusaetzlich ein Vorwaerts und ein 
  80.    Rueckwaertszeiger). Damit werden die Prozeduren remove_at, insert_before
  81.    und insert_after sinnvoll. In der Implementierung wird auf einer Seite
  82.    die struct-Komponente list, bestehend aus den beiden Verweisen 
  83.    zusaetzlich abgespeichert.
  84.  
  85. In Funktionen, die ein Objekt zurueckliefern sollen, jedoch keines zum Liefern 
  86. haben, wird my_no_object als Ruckgabeparameter von benutzt. Weiterhin dient 
  87. my_no_object als Ende-der-Liste Marke im ersten und letzten Element des 
  88. Mappings. Kurzum, my_no_object ist ein Mapping- lokales NO_OBJECT, und dient 
  89. dazu, das Einfuegen von NO_OBJECT zu ermoeglichen.  Stattdessen kann man eben 
  90. my_no_object nicht einfuegen. Faktisch wird my_no_object immer mit dem 
  91. augenblicklich benutzten Mapping initialisiert, so dass ein Mapping nicht in 
  92. sich selbst eingefuegt werden kann. Dieses wird entsprechend abgefangen.
  93. */
  94.  
  95. #define PAGE_SIZE(list_cursor) \
  96.    (list_cursor?page_size_with_list: page_size_without_list)
  97.  
  98. // max_page_entries = die maximale Anzahl an Eintraegen auf einer Seite
  99. #define MAX_PAGE_ENTRIES(list_cursor) \
  100.    (list_cursor? max_page_entries_with_list: max_page_entries_without_list)
  101.  
  102. // aus einer gegebenen Position in der Hashtabelle und der lokalen Tiefe
  103. // der zugehoerigen Seitenliste kann die erste Position in der Hashtabelle
  104. // berechnet werden, die auf diesselbe Seitenliste zeigt.
  105. #define FIRST_LINK(ht_pos,local_depth) \
  106.    ((LSHIFT(1,local_depth)-1) BITAND ht_pos)
  107.  
  108. /* ***********    Implementierung von sos_Map_node    *********************
  109. Ein sos_Map_node enthaelt nur die Komponente sos_Object:key_val, die 
  110. dasjenige Objekt angibt, auf das der Cursor augenblicklich zeigt. 
  111. Ein sos_Map_node ist eindeutig einem Cursor zugeordnet und liegt 
  112. in dessen Container. Ist der Cursor ungueltig, so ist die Komponente 
  113. Cursor->get_key_val() == NO_OBJECT, andernfalls zeigt sie auf einen 
  114. sos_Map_node. Also wird beim Starten auf einem Mapping mit Inhalt ein 
  115. sos_Map_node erzeugt und dem Cursor zugeordnet, beim Verlassen des 
  116. letzten gueltigen Elements wird der sos_Map_node wieder geloescht.
  117. */
  118.  
  119.  
  120. // ************************************************************************** 
  121. sos_Int hash_id (sos_Object o)
  122. // ************************************************************************** 
  123. // benutzt die Adresse des Objektes, um daraus eine Zahl zu basteln
  124.  
  125. // Offsets liegen  nur auf durch 8 teilbaren Addressen
  126. // => die ersten 3 Bit sind nutzlos, wird sie weg.
  127. // Ist das Objekt aber keine Klassen-Instanz, sondern 
  128. // ein externes Objekt (z.B. sos_Int,sos_Char),
  129. // so wird der Offset benutzt, indem der Wert steht.
  130. {  sos_Int h = o.offset();
  131.    if (o.container() != UNUSED_CONTAINER)
  132.       h = RSHIFT(h,3) BITXOR sos_Int(o.container());
  133.     
  134.    return h;
  135. } // ** hash_id **
  136.  
  137.  
  138. // ************************************************************************** 
  139. ht_entry_t read_ht_entry(sos_Container ct, 
  140.                          sos_Offset ht_offset, 
  141.                          sos_Int ht_pos)
  142. // ************************************************************************** 
  143. {  union {sos_Offset dummy;
  144.       char       mem [HT_ENTRY_SIZE];} u;
  145.    ct.read(ht_offset+ht_pos*HT_ENTRY_SIZE, HT_ENTRY_SIZE, &u);
  146.    ht_entry_t ht_entry;
  147.    bcopy_to_sos_Offset(&ht_entry.page_list_offset,&u.mem[0]);
  148.    bcopy_to_sos_Char(&ht_entry.local_depth, &u.mem[SOS_OFFSET_SIZE] );
  149.    return ht_entry;
  150. } // ** read_ht_entry **
  151.  
  152. // ************************************************************************** 
  153. void write_ht_entry(sos_Container ct, 
  154.                     sos_Offset ht_offset, 
  155.                     sos_Int ht_pos, 
  156.                     ht_entry_t ht_entry)
  157. // ************************************************************************** 
  158. {  union {sos_Offset dummy;
  159.       char       mem [HT_ENTRY_SIZE];} u;
  160.  
  161.    bcopy_from_sos_Offset(&ht_entry.page_list_offset, &u.mem[0]);
  162.    bcopy_from_sos_Char(&ht_entry.local_depth, &u.mem[SOS_OFFSET_SIZE]);
  163.    ct.write(ht_offset+ht_pos*HT_ENTRY_SIZE, HT_ENTRY_SIZE, &u);
  164. } // ** write_ht_entry **
  165.  
  166.  
  167. // ************************************************************************** 
  168. page_header_t  read_page_header(sos_Container ct, sos_Offset page_offset) 
  169. // ************************************************************************** 
  170. {  union {sos_Offset dummy;
  171.       char       mem [PAGE_HEADER_SIZE];} u;
  172.  
  173.    page_header_t page_header;
  174.    ct.read (page_offset, PAGE_HEADER_SIZE, &u);
  175.    bcopy_to_sos_Offset(&page_header.next_page, &u.mem[0]);
  176.    bcopy_to_sos_Char(&page_header.pages, &u.mem[SOS_OFFSET_SIZE]);
  177.    bcopy_to_sos_Char(&page_header.entries_on_last_page,
  178.              &u.mem[SOS_OFFSET_SIZE+CHAR_SIZE]);
  179.  
  180.    return page_header;
  181. } // ** read_page_header **
  182.  
  183. // ************************************************************************** 
  184. void write_page_header(sos_Container ct,
  185.                        sos_Offset page_offset, 
  186.                        page_header_t& page_header)
  187. // ************************************************************************** 
  188. {  union {sos_Offset dummy;
  189.       char       mem [PAGE_HEADER_SIZE];} u;
  190.  
  191.    bcopy_from_sos_Offset(&page_header.next_page,&u.mem[0]);
  192.    bcopy_from_sos_Char(&page_header.pages,&u.mem[SOS_OFFSET_SIZE]);
  193.    bcopy_from_sos_Char(&page_header.entries_on_last_page,
  194.                &u.mem[SOS_OFFSET_SIZE+CHAR_SIZE]);
  195.    ct.write (page_offset, PAGE_HEADER_SIZE, &u);
  196. } // ** write_page_header **
  197.  
  198.  
  199. /*
  200. Eine Seitenliste besteht aus einzelnen Seiten des Typs page_t, wobei 
  201. diese durch Vorwaertszeiger verkettet sind. Auf jeder Seite befindet sich 
  202. ein Seitenkopf mit den Angaben:
  203.  
  204.         sos_Char       pages; 
  205.            => Anzahl der Seiten in der Seitenliste
  206.         sos_Char       entries_on_last_page;
  207.            => Eintraege auf der letzten Seite, alle anderen Seite sind
  208.               voll, d.h. sie haben max_page_entries Eintraege. Diese Angabe
  209.               wird nur auf der ersten Seite verwaltet, auf den restlichen
  210.               Seiten ist entries_on_last_page undefiniert.
  211.         sos_Offset next_page;
  212.            => Verweis auf die naechste Seite, bei der letzten Seite 
  213.               undefiniert.
  214. */
  215.  
  216.  
  217. // ************************************************************************** 
  218. void destroy_page_list(sos_Bool      list_cursor,
  219.                        sos_Container ct, 
  220.                        sos_Offset    page_offset,
  221.                        sos_Int       no_of_pages)
  222. // ************************************************************************** 
  223. // deallokiere im Container ct die Seitenliste bestehend aus den
  224. // Typen page_t, wobei die erste zu deallokierende Seite auf page_offset 
  225. // liegt. Insgesamt sind no_of_pages Seiten  zu loeschen.
  226. {  sos_Offset act_page_offset = page_offset;
  227.    sos_Offset next_page_offset;
  228.    for (sos_Int i=1;i<=no_of_pages;i++)
  229.    {     // Lese zuerst naechsten Verweis, bevor die Seite deallokiert wird
  230.       page_header_t page_header = read_page_header(ct, act_page_offset);
  231.       next_page_offset = page_header.next_page;
  232.       
  233.       ct.deallocate(act_page_offset,PAGE_SIZE(list_cursor));
  234.       act_page_offset = next_page_offset;
  235.    } 
  236. } // ** destroy_page_list **
  237.  
  238.  
  239. // ************************************************************************** 
  240. void read_page( sos_Bool      list_cursor,
  241.                 sos_Container ct,
  242.                 sos_Offset    page_offset, 
  243.                 sos_Int       no_of_entries, 
  244.                 page_t&       page)
  245. // ************************************************************************** 
  246. // Lese Seite ab sos_Offset page_offset. Es werden no_of_entries
  247. // Eintraege eingelesen.
  248. {  err_assert((no_of_entries>=0 AND no_of_entries<=MAX_PAGE_ENTRIES(list_cursor)),
  249.       "Mapping:read_page_entry::internal Error");
  250.    page.page_header = read_page_header(ct,page_offset);
  251.    union {sos_Typed_id dummy;
  252.       char         mem [MAX_PAGE_SIZE];} u;
  253.    ct.read(page_offset+PAGE_HEADER_SIZE, no_of_entries*ENTRY_SIZE,&u);
  254.    char *ptr = u.mem;
  255.    for (int i = 0;i<no_of_entries;i++)
  256.    {  bcopy_to_sos_Typed_id(&page.entry[i].key,ptr);
  257.       ptr += SOS_TYPED_ID_SIZE;
  258.       bcopy_to_sos_Typed_id(&page.entry[i].info,ptr);
  259.       ptr += SOS_TYPED_ID_SIZE;
  260.       bcopy_to_sos_Int(&page.entry[i].hash_value,ptr);
  261.       ptr += INT_SIZE;
  262.    } 
  263.  
  264.    if (list_cursor)
  265.    {     // Lese die Vorgaenger und Nachfolger Verweise
  266.       ptr = u.mem;
  267.       ct.read(page_offset+add_list_pos, no_of_entries*LIST_SIZE, &u);
  268.       for (int i = 0; i < no_of_entries; i++)
  269.       {  bcopy_to_sos_Typed_id(&page.list[i].pred,ptr);
  270.          ptr += SOS_TYPED_ID_SIZE;
  271.          bcopy_to_sos_Typed_id(&page.list[i].succ,ptr);
  272.          ptr += SOS_TYPED_ID_SIZE;
  273.       } 
  274.    }
  275. } // ** read_page **
  276.  
  277. // ************************************************************************** 
  278. sos_Int read_page( sos_Bool      list_cursor,
  279.                    sos_Container ct,
  280.                    page_header_t first_page_header, 
  281.                    ht_entry_t    ht_entry, 
  282.                    sos_Int       page_no, 
  283.                    page_t&       page)
  284. // ************************************************************************** 
  285. // Lese die page_no.te Seite, auf die der Hashtabelleneintrag ht_entry
  286. // zeigt, wobei der Seitenkopf der ersten Seite schon unter 
  287. // first_page_header bekannt ist.
  288. {  sos_Offset page_offset = ht_entry.page_list_offset;
  289.    page.page_header = first_page_header;
  290.  
  291.       // Durchlaufe Seitenliste bis zur richtigen Seite
  292.    for (sos_Int no = 1; no < page_no; no++)
  293.    { if (no >1)
  294.          page.page_header = read_page_header(ct,page_offset);
  295.       page_offset =page.page_header.next_page;
  296.    } 
  297.    sos_Int entries = (page_no < first_page_header.pages)?
  298.                      MAX_PAGE_ENTRIES(list_cursor):
  299.                      first_page_header.entries_on_last_page;
  300.    read_page(list_cursor, ct, page_offset, entries, page);
  301.  
  302.    return entries;
  303. } // ** read_page **
  304.  
  305. // ************************************************************************** 
  306. void read_page_entry(sos_Bool      list_cursor,
  307.                      sos_Container ct,
  308.                      sos_Int       page_offset, 
  309.                      sos_Int       entry_no, 
  310.                      page_t&       page)
  311. // ************************************************************************** 
  312. // Lese auf der Seite auf page_offset den entry_no.ten Eintrag in page
  313. {  err_assert((entry_no>=0 AND entry_no<=MAX_PAGE_ENTRIES(list_cursor)),
  314.       "Mapping::read_page_entry::internal Error");
  315.    union {sos_Typed_id dummy;
  316.       char         mem[ENTRY_SIZE];} u; // note: ENTY_SIZE > LIST_SIZE
  317.  
  318.    ct.read( page_offset+PAGE_HEADER_SIZE+entry_no*ENTRY_SIZE,
  319.             ENTRY_SIZE,&u);
  320.    bcopy_to_sos_Typed_id(&page.entry[entry_no].key,&u.mem[0]);
  321.    bcopy_to_sos_Typed_id(&page.entry[entry_no].info,&u.mem[SOS_TYPED_ID_SIZE]);
  322.    bcopy_to_sos_Int(&page.entry[entry_no].hash_value,
  323.             &u.mem[SOS_TYPED_ID_SIZE+SOS_TYPED_ID_SIZE]);
  324.  
  325.    if (list_cursor)
  326.    {  ct.read( page_offset+add_list_pos+entry_no*LIST_SIZE,
  327.                LIST_SIZE,&u);
  328.       bcopy_to_sos_Typed_id(&page.list[entry_no].pred,&u.mem[0]);
  329.       bcopy_to_sos_Typed_id(&page.list[entry_no].succ,
  330.                             &u.mem[SOS_TYPED_ID_SIZE]);
  331.    }
  332. } // ** read_page_entry **
  333.  
  334. // ************************************************************************** 
  335. void write_page(sos_Bool      list_cursor,
  336.                 sos_Container ct, 
  337.                 sos_Offset    page_offset,
  338.                 sos_Int       no_of_entries, 
  339.                 page_t&       page)
  340. // ************************************************************************** 
  341. // Schreibe die Seite page mit no_of_entries Eintraegen 
  342. // an die Stelle page_offset
  343. {  write_page_header(ct,page_offset,page.page_header);
  344.    err_assert((no_of_entries>=0 AND no_of_entries<=MAX_PAGE_ENTRIES(list_cursor)),
  345.       "Mapping::write_page::internal Error");
  346.  
  347.    union {sos_Typed_id dummy;
  348.       char           mem [MAX_PAGE_SIZE];} u;
  349.    char *ptr = u.mem;
  350.    for (int i = 0; i < no_of_entries; i++)
  351.    {  bcopy_from_sos_Typed_id(&page.entry[i].key,ptr);
  352.       ptr += SOS_TYPED_ID_SIZE;
  353.       bcopy_from_sos_Typed_id(&page.entry[i].info,ptr);
  354.       ptr += SOS_TYPED_ID_SIZE;
  355.       bcopy_from_sos_Int(&page.entry[i].hash_value,ptr);
  356.       ptr += INT_SIZE;
  357.    } 
  358.    ct.write(page_offset+PAGE_HEADER_SIZE, no_of_entries*ENTRY_SIZE,&u);
  359.  
  360.    if (list_cursor)
  361.    {  ptr = u.mem;
  362.       for (int i = 0; i < no_of_entries; i++)
  363.       {  bcopy_from_sos_Typed_id(&page.list[i].pred,ptr);
  364.          ptr += SOS_TYPED_ID_SIZE;
  365.          bcopy_from_sos_Typed_id(&page.list[i].succ,ptr);
  366.          ptr += SOS_TYPED_ID_SIZE;
  367.       }
  368.       ct.write(page_offset+add_list_pos, LIST_SIZE*no_of_entries, &u);
  369.    }
  370. } // ** write_page **
  371.  
  372. // ************************************************************************** 
  373. void write_page_entry(sos_Bool      list_cursor,
  374.                       sos_Container ct, 
  375.                       sos_Int       page_offset, 
  376.                       sos_Int       entry_no, 
  377.                       page_t&       page)
  378. // ************************************************************************** 
  379. // Schreibe auf der Seite page den einzelnen Eintrag Nr entry_no
  380. // auf die Platte, der Seitenanfang beginnt bei page_offset.
  381. {  err_assert((entry_no>=0 AND entry_no<=MAX_PAGE_ENTRIES(list_cursor)),
  382.       "Mapping::write_page::internal Error");
  383.    union {sos_Typed_id dummy;
  384.       char         mem[ENTRY_SIZE];} u; // note: ENTY_SIZE > LIST_SIZE
  385.  
  386.    bcopy_from_sos_Typed_id(&page.entry[entry_no].key,&u.mem[0]);
  387.    bcopy_from_sos_Typed_id(&page.entry[entry_no].info,
  388.                            &u.mem[SOS_TYPED_ID_SIZE]);
  389.    bcopy_from_sos_Int(&page.entry[entry_no].hash_value,
  390.               &u.mem[SOS_TYPED_ID_SIZE+SOS_TYPED_ID_SIZE]);
  391.  
  392.    ct.write( page_offset+PAGE_HEADER_SIZE+entry_no*ENTRY_SIZE,
  393.              ENTRY_SIZE,&u);
  394.    if (list_cursor)
  395.    {  bcopy_from_sos_Typed_id(&page.list[entry_no].pred,&u.mem[0]);
  396.       bcopy_from_sos_Typed_id(&page.list[entry_no].succ,
  397.                               &u.mem[SOS_TYPED_ID_SIZE]);
  398.       ct.write( page_offset+add_list_pos+entry_no*LIST_SIZE, LIST_SIZE,&u);
  399.    }   
  400. } // ** write_page_entry **
  401.  
  402. // search_page_for_key__F8sos_BoolR6page_tiiG10sos_Object
  403. // ************************************************************************** 
  404. sos_Int search_page_for_key(sos_Bool     key_based_on_equal, 
  405.                             page_t&      page, 
  406.                             sos_Int      entries, 
  407.                             sos_Int      org_hash_value, 
  408.                             sos_Object   key)
  409. // ************************************************************************** 
  410. // durchsucht die Seite page mit entries Eintraegen nach dem sos_Object key,
  411. // das den Hashwert org_hash_value besitzt. Wird es gefunden, wird seine
  412. // Position in der Seite geliefert, ansonsten -1.
  413. {  T_PROC("search_page_for_key");
  414.    TT(agg_M, T_ENTER);
  415.  
  416.    sos_Bool found = FALSE;
  417.    for (sos_Int i=0;
  418.         ((i<entries) AND (NOT found));
  419.         i++)
  420.    {  if (page.entry[i].hash_value == org_hash_value)
  421.       {  sos_Object o = make_Object(page.entry[i].key);
  422.          if (agg_same_entity(o, key, key_based_on_equal, EQ_STRONG))
  423.          {  found = TRUE;
  424.             TT(agg_M, T_LEAVE);
  425.             return i;
  426.          }
  427.       }
  428.    } 
  429.  
  430.    TT(agg_M, T_LEAVE);
  431.    return -1;
  432. } // ** search_page_for_key **
  433.  
  434. // ************************************************************************** 
  435. sos_Offset new_page_list(sos_Container ct, sos_Bool list_cursor)
  436. // ************************************************************************** 
  437. // allokiere eine neue Seitenliste und liefere deren sos_Offset zurueck
  438. {  T_PROC("new_page_list");
  439.    TT(agg_L, T_ENTER);
  440.  
  441.    sos_Offset new_page_offset = ct.allocate(PAGE_SIZE(list_cursor));
  442.    page_header_t page_header;
  443.    page_header.entries_on_last_page = 0;
  444.    page_header.pages = 1;
  445.    write_page_header(ct,new_page_offset, page_header);
  446.  
  447.    TT(agg_L, T_LEAVE);
  448.    return new_page_offset;
  449. } // ** new_page_list **
  450.  
  451. // ************************************************************************** 
  452. void sos_Object_sos_Object_Mapping::write_succ_pred(
  453.                                       sos_Container ct,
  454.                                       sos_Bool      key_based_on_equal,
  455.                                       sos_Bool      list_cursor,
  456.                                       sos_Object    key, 
  457.                                       sos_Bool      write_succ, 
  458.                                       sos_Object    succ_pred)
  459. // ************************************************************************** 
  460. // Schreibe in den Vorgaeger bzw. Nachfolger von key succ_pred.
  461. // Ob Vor oder Nachgaenger ausgewaehlt wird, wird durch write_succ 
  462. // geregelt. write_succ == TRUE schreibt succ_pred in den 
  463. // Nachfolgerzeiger von key, ansonsten in den Vorgaengerzeiger von key.
  464. {  T_PROC("Mapping::write_succ_pred");
  465.    TT(agg_M, T_ENTER);
  466.    sos_Object my_no_object = self;
  467.    if (my_no_object == key)
  468.    {  TT(agg_M, T_LEAVE);
  469.       return;
  470.    }
  471.    
  472.    sos_Int org_hash_value = absolute((key_based_on_equal)?
  473.                                       key.hash_value():hash_id(key));
  474.    sos_Int ht_pos = org_hash_value MOD self.get_ht_entries();
  475.    ht_entry_t ht_entry = read_ht_entry(ct,self.get_ht_offset(),ht_pos);
  476.  
  477.    sos_Offset page_offset = ht_entry.page_list_offset;
  478.    page_header_t first_page_header = read_page_header(ct, page_offset);
  479.    sos_Int pages = first_page_header.pages;
  480.    sos_Int entries_on_last_page = first_page_header.entries_on_last_page;
  481.  
  482.    sos_Int pos = -1; // entspricht "nicht gefunden"
  483.    sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  484.    page_t page;
  485.    for (sos_Int page_no = 1;
  486.         (page_no<=pages) AND (pos == -1);
  487.         page_no++)
  488.    {  if (page_no == pages)
  489.      entries_on_page = entries_on_last_page;
  490.  
  491.       read_page(TRUE, ct, page_offset, entries_on_page, page);
  492.       sos_Int pos = search_page_for_key ( key_based_on_equal,page, 
  493.                                           entries_on_page,
  494.                                           org_hash_value, key );
  495.       if (pos == -1)
  496.          page_offset = page.page_header.next_page;
  497.       else
  498.       {     // Objekt gefunden
  499.          if (write_succ)
  500.             page.list[pos].succ = make_object_save(succ_pred);
  501.          else
  502.             page.list[pos].pred = make_object_save(succ_pred);
  503.          write_page_entry(TRUE, ct,page_offset,pos, page);
  504.       }
  505.    } 
  506.    TT(agg_M, T_LEAVE);
  507. } // ** Mapping::write_succ_pred **
  508.  
  509.  
  510. // ************************************************************************** 
  511. sos_Offset increase_page_list( sos_Bool       list_cursor,
  512.                                sos_Container  ct, 
  513.                                sos_Offset     first_page_offset,
  514.                                page_header_t& first_page_header,
  515.                                sos_Offset     last_page_offset)
  516. // ************************************************************************** 
  517. // Eine Seitenliste, die an der Stelle ht_pos an der Hashtabelle
  518. // angehaengt ist, wird um eine Seite erweitert. diese Seite wird
  519. // hinten angehaengt. Ein Verweis auf die bisher letzte Seite 
  520. {  T_PROC("increase_page_list");
  521.    TT(agg_M, T_ENTER);
  522.  
  523.    sos_Offset new_page_offset = ct.allocate(PAGE_SIZE(list_cursor));
  524.  
  525.       // Eigentlich sollte der Fall der Seitenlisten gaenzlich vermieden
  526.       // werden. Wird nun eine Seitenliste tatsaechlich ueber 126 Seiten
  527.       // gross, so ist entweder die Statistik fehlerhaft, oder es
  528.       // sind tatsaechlich mehr als 3225 Eintraege mit demselben Hashwert im
  529.       // Mapping. Diese Faelle fuehren zum Absturz, da die Variable, die die
  530.       // Seiten in einer Seitenliste zaehlt, ein char ist. Ansich ist eine
  531.       // solche Konstellation jedoch nicht vorstellbar.
  532.    if (first_page_header.pages >= 126)
  533.       err_raise(err_SYS, "statistical Error","Mapping:insert");
  534.  
  535.    first_page_header.pages++;
  536.    first_page_header.entries_on_last_page = 0;
  537.   
  538.       // Existierte bisher nur eine Seite ?
  539.    if (first_page_header.pages == 2)
  540.       first_page_header.next_page = new_page_offset;
  541.    else
  542.    {     // Es gab schon mehr als eine Seite, der erste Seitenheader und 
  543.          // der Header der bisher letzten Seite muss geschrieben werden
  544.       page_header_t last_page_header;
  545.       last_page_header.next_page = new_page_offset;
  546.       write_page_header(ct,last_page_offset, last_page_header);
  547.    }
  548.    write_page_header(ct,first_page_offset, first_page_header);
  549.  
  550.    TT(agg_M, T_LEAVE);
  551.    return new_page_offset;
  552. } // ** Mapping::increase_page_list
  553.  
  554. /*
  555. Um zu entscheiden, ob die Hashtabelle geschrumpft werden kann, muss bekannt 
  556. sein, ob es Seitenlisten gibt, auf die nur ein HT-Eintrag verweist. Falls ja,
  557. ist ein Schrumpfen nicht moeglich. Da beim Teilen und Splitten einer Seite
  558. die lokale Tiefe veraendert wird, muss fuer jede moegliche lokale Tiefe 
  559. die Anzahl der Verweise gespeichert werden, da beim Splitten 2 Seiten
  560. mit hoeheren lokalen Tiefen dazukommen und eine mit einer niedrigeren weg-
  561. faellt. 
  562. Es gibt also einen von Hand allokierten Platz, auf dessen Anfang 
  563. get_no_of_pages_offset() zeigt. In den ersten 4 Byte davon steht die Anzahl 
  564. der Seitenlisten mit lokaler Tiefe 0 , in den naechsten 4 Byte die Anzahl mit
  565. lokaler Tiefe 1 etc. bis MAX_GLOBAL_DEPTH.
  566. */
  567.  
  568. // ************************************************************************** 
  569. sos_Bool no_single_referenced_pages(sos_Container ct, 
  570.                                     sos_Offset    no_of_pages_offset, 
  571.                                     sos_Int       global_depth)
  572. // ************************************************************************** 
  573. // liefert TRUE, falls es keine Seitenliste gibt, die von der Hashtabelle
  574. // nur von einem einzigen Verweis referenziert wird. Dies wird anhand
  575. // der Zaehler festgestellt, die fuer jede lokale Tiefe zaehlen, wieviel
  576. // Seitenlisten es mit dieser lokalen Tiefe gibt. Die Seitenlisten,  die
  577. // nur von einem Verweis referenziert werden, zeichnen sich durch  
  578. // lokale Tiefe == globale Tiefe aus.
  579. {  sos_Int entry;
  580.    union {sos_Int dummy;
  581.       char    mem [INT_SIZE];} u;
  582.       // lese die Anzahl der Verweise auf Seitenlisten der lokalen 
  583.       // Tiefe global_depth
  584.    ct.read(no_of_pages_offset+INT_SIZE*global_depth,INT_SIZE,&u);
  585.    bcopy_to_sos_Int(&entry,&u); 
  586.    return sos_Bool (entry == 0);
  587. } // ** Mapping::no_single_referenced_pages **
  588.  
  589. // ************************************************************************** 
  590. void add_no_of_pages(sos_Container ct, 
  591.                      sos_Offset    no_of_pages_offset, 
  592.                      sos_Int       local_depth, 
  593.                      sos_Int       value)
  594. // ************************************************************************** 
  595. // zaehle zu der Anzahl von Verweisen auf eine Seitenliste mit der
  596. // lokalen Tiefe local_depth value dazu.
  597. {  sos_Int entry;
  598.    union {sos_Int dummy;
  599.       char    mem [INT_SIZE];} u;
  600.  
  601.    sos_Int offset = no_of_pages_offset+INT_SIZE*local_depth;
  602.    ct.read(offset, INT_SIZE, &u);
  603.    bcopy_to_sos_Int(&entry,&u);
  604.    entry += value;
  605.    bcopy_from_sos_Int(&entry,&u);
  606.    ct.write(offset, INT_SIZE, &u);
  607. } // ** add_no_of_page **
  608.  
  609.  
  610. // ************************************************************************** 
  611. void sos_Object_sos_Object_Mapping::insert_in_page_list (
  612.                                         sos_Container ct,
  613.                                         sos_Bool      key_based_on_equal,
  614.                                         sos_Bool      list_cursor,
  615.                                         sos_Offset    page_list_offset, 
  616.                                         sos_Int       org_hash_value, 
  617.                                         sos_Object key, sos_Object info,
  618.                                         sos_Object pred, sos_Object succ)
  619. // ************************************************************************** 
  620. // traegt einen Eintrag in eine Seitenliste ein und ersetzt
  621. // geg. einen alten. Auf der Seitenliste muss Platz sein
  622. {  T_PROC("Mapping::insert_in_page_list");
  623.  
  624.    page_t page;
  625.    sos_Offset page_offset = page_list_offset;
  626.    
  627.       // Befindet sich der key bereits auf der Seite, so wird er durch
  628.       // den neuen Eintrag ersetzt. Schaue also nach
  629.    
  630.    sos_Int pos = -1; // entspricht "nicht gefunden"
  631.    sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  632.  
  633.    page.page_header = read_page_header(ct,page_offset);
  634.  
  635.    page_header_t first_page_header = page.page_header;
  636.    sos_Int pages = first_page_header.pages;
  637.    sos_Int entries_on_last_page = first_page_header.entries_on_last_page;
  638.    for (sos_Int page_no=1; 
  639.         (page_no <= pages) AND (pos == -1); 
  640.         page_no++)
  641.    {  if (page_no == pages)
  642.      entries_on_page = entries_on_last_page;
  643.       read_page(list_cursor, ct,page_offset, entries_on_page, page);
  644.       pos = search_page_for_key (key_based_on_equal, page, 
  645.                                  entries_on_page, org_hash_value,key);
  646.       if ((pos == -1) AND (page_no < pages))
  647.          page_offset = page.page_header.next_page;
  648.    } 
  649.  
  650.       // Falls der Eintrag ersetzt wird, so wird er an diese
  651.       // Stelle eingesetzt. Ansonsten wird er auf der
  652.       // letzten Seite eingetragen und die H-Tabelle korrigiert
  653.  
  654.    sos_Int write_pos = pos;
  655.    if (pos == -1)
  656.    {     // Eintrag nicht gefunden, also schreibe ihn auf die letzte Seite.
  657.          // Da die gesamte Liste durchgegangen wurde, ist page_offset
  658.          // die Adresse der letzten Seite.
  659.       
  660.          // korrigiere Seitenheader der ersten Seite
  661.       first_page_header.entries_on_last_page++;
  662.       write_page_header(ct,page_list_offset,first_page_header);
  663.  
  664.       write_pos = entries_on_page;
  665.       self.set_cardinality(self.get_cardinality() + 1);
  666.    }
  667.  
  668.    page.entry[write_pos].hash_value = org_hash_value;
  669.       // Falls der Key existiert wird er nicht nochmal eingetragen,
  670.       // sondern nur der Entity ersetzt
  671.    if (write_pos != pos)
  672.       page.entry[write_pos].key = make_object_save(key);
  673.    page.entry[write_pos].info = make_object_save(info);
  674.  
  675.       // Schreibe die Liste evt auf die Seite zurueck
  676.    if (pos == -1)
  677.    {  if (list_cursor)
  678.       {     // schreibe in die Liste succ und pred
  679.          page.list[write_pos].succ = make_object_save(succ);
  680.          page.list[write_pos].pred = make_object_save(pred);
  681.             // aktualisiere den Vorwaertszeiger von pred und den 
  682.             // Rueckwaertszeiger von succ
  683.          self.write_succ_pred
  684.             (ct, key_based_on_equal, list_cursor, pred, TRUE, key);
  685.          self.write_succ_pred
  686.             (ct, key_based_on_equal, list_cursor, succ, FALSE, key);
  687.  
  688.          if (self.get_cardinality() == 1)
  689.          {     // erstes Element wird eingefuegt
  690.             self.set_first_object(key);
  691.             self.set_last_object(key);
  692.          }
  693.          else
  694.          {  if (self.get_first_object() == succ)
  695.                self.set_first_object(key);
  696.             if (self.get_last_object() == pred)
  697.                self.set_last_object(key);
  698.          }
  699.       }
  700.  
  701.          // schreibe den Eintrag auf der Seite zurueck
  702.       write_page_entry(list_cursor, ct,page_offset, write_pos, page);
  703.    }
  704.    else
  705.          // Der Eintrag war bereits vorhanden, nur der Entity wurde geaendert
  706.          // schreibe den Eintrag auf der Seite zurueck
  707.       write_page_entry(list_cursor, ct,page_offset, write_pos, page);
  708.  
  709.    TT(agg_M, T_LEAVE);
  710. } // ** Mapping::insert_in_page_list **
  711.  
  712.  
  713.  
  714. // ************************************************************************** 
  715. void sos_Object_sos_Object_Mapping::split_page(sos_Container ct, 
  716.                                                sos_Bool      list_cursor, 
  717.                                                sos_Offset    page_list_offset,
  718.                                                sos_Char      par_local_depth,
  719.                                                sos_Int       org_hash_value, 
  720.                                                sos_Int       nec_local_depth)
  721. // ************************************************************************** 
  722. // Eine Seitenliste wird solange gesplittet, bis der Seitenliste
  723. // die neue lokale Tiefe nec(cessary)_local_depth zugeordnet wird.
  724. // Saemtliche Seitenteilungen vor der letzten sind Seitenteilungen
  725. // ohne Bewegungen von Objekten, denn wuerden Objekte bewegt,
  726. // wuerde Platz geschaffen und somit waere nec_local_depth kleiner.
  727. {  T_PROC("Mapping::split_page");
  728.    TT(agg_M, T_ENTER);
  729.  
  730.    sos_Int global_depth = self.get_global_depth();
  731.    sos_Offset no_of_pages_offset = self.get_no_of_pages_offset();
  732.    sos_Offset ht_offset = self.get_ht_offset();
  733.  
  734.    sos_Int max_page_entries = MAX_PAGE_ENTRIES(list_cursor);
  735.       // Teile die Seitenliste sooft wie noetig, d.h. allokiere neue
  736.       // Seiten und biege die richtigen HT-Eintraege auf diese
  737.       // Seiten um
  738.    for (;par_local_depth <nec_local_depth;)
  739.    {     // erzeuge neue leere Seite
  740.       ht_entry_t new_ht_entry;
  741.       new_ht_entry.page_list_offset = new_page_list(ct, list_cursor);
  742.       sos_Int local_depth           = par_local_depth;
  743.       sos_Int new_local_depth       = ++par_local_depth;
  744.       new_ht_entry.local_depth      = new_local_depth;
  745.       self.set_no_of_page_lists(self.get_no_of_page_lists() + 1);
  746.       self.set_no_of_pages(self.get_no_of_pages() + 1);
  747.  
  748.       add_no_of_pages(ct,no_of_pages_offset,local_depth,-1);
  749.       add_no_of_pages(ct,no_of_pages_offset,new_local_depth,2);
  750.  
  751.          // biege alle Eintraege der HT mit gesetztem
  752.          // new_local_depth.ten Bit auf die neue Seite um
  753.  
  754.          // Wie lautet der der neuen Seite zugeordnete Hash-Wert-Teil ?
  755.          // Nimm den alten Hash-Teil
  756.       sos_Int old_hash_value_part = org_hash_value BITAND 
  757.                                     (LSHIFT(1,local_depth)-1); 
  758.  
  759.          // Laufe alle Indexe durch, bei denen ein Verweis
  760.          // auf die zu teilende Seitenliste steht. Das sind
  761.          // 2^(global_depth-local_depth) Stueck.
  762.  
  763.          // Die Verweise werden abwechselnd belassen und umgebogen.
  764.          // Da auf der alten Seitenliste die ersten nec_local_depth
  765.          // Bit gleich sind, wird so begonnen, dass die alte Seitenliste
  766.          // immer noch von der gleichen Stelle der 
  767.          // H-Tabelle erreicht wird (new_link)
  768.       sos_Bool new_link = FALSE; // starte bei alter Seitenliste
  769.       if ((org_hash_value BITAND LSHIFT(1,local_depth)) != 0)
  770.          new_link = TRUE; // starte bei leerer Seite
  771.  
  772.          // wo ist der erste Verweis auf diese Seitenliste ?
  773.       for (sos_Int k = 0;k<LSHIFT(1,global_depth-local_depth); k++)
  774.       {     // verschiebe Laufindex k an richtige Position 
  775.             // vor dem Wert der Seite
  776.          sos_Int j = LSHIFT(k,local_depth);
  777.             // addiere den Hash-Teil der Seite dazu
  778.          j = j BITOR old_hash_value_part;
  779.          
  780.          if (new_link)
  781.                // Dieser Eintrag muss auf die neue 
  782.                // leere Seite umgebogen werden
  783.             write_ht_entry(ct, ht_offset, j, new_ht_entry);
  784.          else
  785.          {     // Dieser Eintrag verbleibt,
  786.                // lediglich die lokale Tiefe wird geaendert
  787.             ht_entry_t tmp_ht_entry = read_ht_entry(ct, ht_offset, j);
  788.             tmp_ht_entry.local_depth ++;
  789.             write_ht_entry(ct,ht_offset,j, tmp_ht_entry);
  790.          }
  791.          new_link = (sos_Bool) (NOT new_link);
  792.       } 
  793.    } 
  794.  
  795.       // Da nur die letzte Seitenteilung hierbei beteiligt ist,
  796.       // muessen also Seiteneintraege der alten Seitenliste 
  797.       // auf die bis jetzt leere Partnerseite. 
  798.       // Berechne Hash-Teil der alten Seitenliste
  799.    sos_Int hash_value_part = org_hash_value BITAND 
  800.                              (LSHIFT(1,nec_local_depth)-1);
  801.       // invertiere das nec_local_depth.te Bit => Partnerseite 
  802.    sos_Int ht_partner_pos = hash_value_part BITXOR 
  803.                             LSHIFT(1,nec_local_depth-1);
  804.    
  805.       // Lese den Offset der Partnerseite
  806.    ht_entry_t ht_partner_entry = read_ht_entry(ct,ht_offset,ht_partner_pos);
  807.       // Also: Die Eintraege kommen von ht_entry.page_list_offset 
  808.       //       nach ht_partner_entry.page_list_offset
  809.  
  810.       // Gehe die alte Seitenliste durch und schiebe jeden Seiteneintrag,
  811.       // dessen Hashwert ein anderes nec_local_depth.tes Bit aufweist
  812.       // als in org_hash_value, auf die neue Seitenliste
  813.  
  814.    sos_Offset old_page_offset  = page_list_offset;
  815.    sos_Offset read_page_offset = old_page_offset;
  816.    sos_Offset new_page_offset  = ht_partner_entry.page_list_offset;
  817.    sos_Int bit                 = LSHIFT(1,nec_local_depth-1);
  818.    sos_Int should_be_bit       = org_hash_value BITAND bit;
  819.  
  820.    page_t old_page;
  821.    page_header_t old_page_header = read_page_header(ct,old_page_offset);
  822.    old_page.page_header =    old_page_header;
  823.    sos_Int old_entry_no     = 0;
  824.    sos_Int old_page_no      = 1;
  825.    sos_Bool add_old_page    = FALSE;
  826.  
  827.    page_t new_page;
  828.    sos_Int new_entry_no     = 0;
  829.    sos_Int new_page_no      = 1;
  830.  
  831.    page_header_t new_page_header = read_page_header(ct,new_page_offset);
  832.    new_page.page_header = new_page_header;
  833.  
  834.    page_t r_page;
  835.    page_header_t r_page_header = read_page_header(ct,read_page_offset);
  836.  
  837.    sos_Int no_of_pages = self.get_no_of_pages();
  838.    for (sos_Int read_page_no=1;
  839.         read_page_no <= r_page_header.pages;
  840.         read_page_no++)
  841.    {  sos_Int read_entries = (r_page_header.pages > read_page_no)?
  842.                           max_page_entries:r_page_header.entries_on_last_page;
  843.       read_page(list_cursor, ct,read_page_offset, read_entries, r_page);
  844.       read_page_offset = r_page.page_header.next_page;
  845.  
  846.          // Gehe die alte Seite durch und kopiere die passenden Eintraege
  847.          // auf die neue Seite. 
  848.       for (sos_Int read_no=0;read_no<read_entries;read_no++) 
  849.       {  if ((r_page.entry[read_no].hash_value BITAND bit) !=should_be_bit)
  850.             {     // gesetztes  Bit => Eintrag auf neue Seite
  851.  
  852.                   // Ist neue Seite schon vollstaendig beschrieben ?
  853.                if (new_entry_no == max_page_entries)
  854.                {     // Falls die neue Seite bereits voll ist, erweitere Liste
  855.                   sos_Offset last_page = 
  856.                      increase_page_list(list_cursor, ct, 
  857.                                         ht_partner_entry.page_list_offset,
  858.                                         new_page_header, new_page_offset);
  859.  
  860.                   no_of_pages++;
  861.                   new_page.page_header = new_page_header;
  862.                   new_page.page_header.next_page = last_page;
  863.  
  864.                      // und schreibe die volle Seite aus
  865.                   write_page(list_cursor, ct, new_page_offset, 
  866.                             max_page_entries, new_page);
  867.  
  868.                   new_entry_no = 0;
  869.                   new_page_offset = last_page;
  870.                   new_page_no++;
  871.  
  872.                }
  873.                new_page.entry[new_entry_no] = r_page.entry[read_no]; 
  874.                   // Falls list_cursor == FALSE schadet 
  875.                   // die folgende Zeile nichts
  876.                new_page.list[new_entry_no++] = r_page.list[read_no];
  877.             }
  878.          else
  879.             {     // Ist die alte Seite schon vollstaendig beschrieben ?
  880.                if (old_entry_no == max_page_entries)
  881.                {     // Ja, schreibe alte volle Seite aus
  882.                   write_page(list_cursor, ct,
  883.                              old_page_offset, max_page_entries, old_page);
  884.  
  885.                   old_page_no++;
  886.                   old_page_offset = old_page.page_header.next_page;
  887.  
  888.                      // Lese den Vorwaertsverweis der naechsten Seite
  889.                   if (old_page_no < old_page_header.pages)
  890.                     old_page.page_header=read_page_header(ct,old_page_offset);
  891.  
  892.                   old_entry_no = 0;
  893.                }
  894.                old_page.entry[old_entry_no] = r_page.entry[read_no];
  895.                   // Falls list_cursor == FALSE schadet 
  896.                   // die folgende Zeile nichts
  897.                old_page.list[old_entry_no++] = r_page.list[read_no];
  898.             }
  899.       } 
  900.    } 
  901.                   
  902.    self.set_no_of_pages(no_of_pages);
  903.  
  904.       // Falls eine neue Seite noch nicht ausgeschrieben ist, tue dies
  905.    if (new_entry_no > 0)
  906.    {  new_page.page_header.entries_on_last_page = new_entry_no;
  907.       new_page.page_header.pages = new_page_no;
  908.       write_page(list_cursor, ct,new_page_offset, new_entry_no, new_page);
  909.    }
  910.  
  911.       // Korrigiere Seitenheader der ersten neuen Seite
  912.    new_page_header.entries_on_last_page = new_entry_no;
  913.    new_page_header.pages = new_page_no;
  914.  
  915.       // Schreibe evt. den Seitenheader
  916.    if ((new_page_header.pages > 1) OR (new_entry_no == 0))
  917.       write_page_header(ct,ht_partner_entry.page_list_offset,new_page_header);
  918.  
  919.  
  920.       // Falls eine alte Seite noch nicht ausgeschrieben wurde, tue dies
  921.    if (old_entry_no > 0)
  922.    {  old_page.page_header.entries_on_last_page = old_entry_no;
  923.       old_page.page_header.pages = old_page_no;
  924.       write_page(list_cursor, ct,old_page_offset, old_entry_no, old_page);
  925.    }
  926.  
  927.       // Falls die alte Seitenliste eine volle Liste ist, lasse eine
  928.       // leere Seite dranhaengen, da auf der alten Seitenliste ein
  929.       // neuer Eintrag erfolgen soll.
  930.    if (old_entry_no == max_page_entries)
  931.    {  old_entry_no = 0;
  932.       old_page_no++;
  933.       add_old_page = TRUE;
  934.    }
  935.  
  936.       // Korrigiere Seitenheader der ersten alten Seite
  937.    old_page_header.entries_on_last_page = old_entry_no;
  938.    old_page_header.pages = old_page_no;
  939.  
  940.       // Schreibe evt. alten Seitenheader
  941.    if ((old_page_header.pages > 1) OR (old_entry_no == 0))
  942.       write_page_header(ct,page_list_offset, old_page_header);
  943.  
  944.       // Gebe den Rest der alten Seitenliste frei
  945.    if (old_page_no < r_page_header.pages) 
  946.    {  destroy_page_list(list_cursor, ct, old_page.page_header.next_page, 
  947.                         r_page_header.pages-old_page_no);
  948.       self.set_no_of_pages(no_of_pages - (r_page_header.pages - old_page_no));
  949.    }
  950.    TT(agg_M, T_LEAVE);
  951. } // ** Mapping::split_page **
  952.  
  953.  
  954. // ************************************************************************** 
  955. void sos_Object_sos_Object_Mapping::increase_hash_table()
  956. // ************************************************************************** 
  957. // erweitere die gesamte Hash-Tabelle, d.h. allokiere
  958. // doppelt soviel Platz wie jetzt belegt wird, kopiere
  959. // die alte Hash-Tabelle in die erste Haelfte und danach
  960. // in die zweite Haelfte. => Auf jede Seite
  961. // existieren zwei Verweise. Wirf die alte Hashtabelle weg
  962. {  T_PROC("Mapping::increase_hash_table");
  963.    TT(agg_M, T_ENTER);
  964.    sos_Container ct = self.container(); 
  965.    sos_Int old_ht_entries = self.get_ht_entries();
  966.    sos_Int old_ht_size = old_ht_entries*HT_ENTRY_SIZE;
  967.    sos_Offset new_ht_offset = ct.allocate(old_ht_size*2);
  968.  
  969.       // kopiere bisherige Hashtabelle zweimal 
  970.       // hintereinander in den neu allokierten Platz
  971.    ct.copy(self.get_ht_offset(), old_ht_size, ct, new_ht_offset);
  972.    ct.copy(self.get_ht_offset(), old_ht_size, ct, new_ht_offset+old_ht_size);
  973.  
  974.       // Wirf alte Hash-tabelle weg
  975.    ct.deallocate(self.get_ht_offset(), old_ht_size);
  976.  
  977.       // markiere die Neue
  978.    self.set_ht_offset(new_ht_offset);
  979.    self.set_ht_entries(old_ht_entries * 2);
  980.    self.set_global_depth(self.get_global_depth() + 1);
  981.    TT(agg_M, T_LEAVE);
  982. } // ** Mapping::increase_hash_table **
  983.  
  984. // increase_ht_structur__F8sos_Booliiiiii
  985. // ************************************************************************** 
  986. sos_Bool increase_ht_structur(sos_Bool list_cursor,
  987.                               sos_Int global_depth, 
  988.                               sos_Int ht_entries,
  989.                               sos_Int no_of_pages,
  990.                               sos_Int length,
  991.                               sos_Int local_depth, 
  992.                               sos_Int nec_local_depth)
  993. // ************************************************************************** 
  994. // entscheidet, ob wegen eines Seitenueberlaufs die HT-Struktur
  995. // vergoessert werden soll, oder an die Seitenliste eine Seite
  996. // angehaengt wird.
  997. {  
  998.    T_PROC("increase_ht_structur");
  999.    TT(agg_M, T_ENTER);
  1000.  
  1001.       // Falls die HT nicht vergroessert werden muesste, sondern 
  1002.       // eine Seitenteilung reichen wuerde, plaediere immer fuer die
  1003.       // Erweiterung der HT
  1004.    if (global_depth >= nec_local_depth)
  1005.    {  TT(agg_M, T_LEAVE)
  1006.       return TRUE;
  1007.    }
  1008.  
  1009.       // Berechne den Platzbedarf bei Vergroesserung der HT-Struktur
  1010.    sos_Int page_size = PAGE_SIZE(list_cursor);
  1011.    sos_Int ht_memory; // Bei HT-Erweiterung
  1012.    sos_Int pl_memory; // Bei Seitenlisten Erweiterung
  1013.    
  1014.       // Bei normaler  Speicherausnutzung, d.h. Jede Seite ist 
  1015.       // zur Haelfte gefuellt, gibt die Kennzahl 100, sonst > 100
  1016.       // Ist die Ausnutzung besser, gilt Kennzahl < 100
  1017.  
  1018.       // Bedarf der jetzigen Hashtabelle
  1019.    sos_Int ht_use = ht_entries*HT_ENTRY_SIZE;
  1020.   
  1021.       // Bedarf der jetzigen saemtlichen Seiten
  1022.    sos_Int page_lists_use = no_of_pages*page_size;
  1023.  
  1024.       // Berechne den Speicher, der beim Erweitern der HT-Struktur
  1025.       // zusaetzlich benoetigt wird
  1026.  
  1027.       // Fuer jedes Splitten kommt eine Seite dazu
  1028.    sos_Int increasing_use = (nec_local_depth-local_depth)*page_size;
  1029.       // Fuer das Erweitern der HT kommt immer die bisherige Groesse dazu
  1030.    increasing_use += (LSHIFT(1,nec_local_depth) - LSHIFT(1,global_depth))
  1031.                      *HT_ENTRY_SIZE;
  1032.  
  1033.    sos_Int ht_memory_used = ht_use + page_lists_use + increasing_use;
  1034.       // Bei der Alternative der Seitenliste kommt nur eine Seite dazu;
  1035.    sos_Int pl_memory_used = ht_use + page_lists_use + page_size;
  1036.  
  1037.       // Berechne den optimalen Platzbedarf. Er ergibt sich durch 
  1038.       // zu drei/viertel gefuellte Seiten, wobei jeder Verweis auf genau
  1039.       // eine Seite zeigt.=> Berechne Anzahl der noetigen Seiten = Verweise,
  1040.       // plumitiziere mit Platzbedarf
  1041.    sos_Int opt_entries = MAX_PAGE_ENTRIES(list_cursor)*3/4;
  1042.    sos_Int opt_memory_used = (page_size + HT_ENTRY_SIZE)*
  1043.                          length/opt_entries;
  1044.  
  1045.    ht_memory = (ht_memory_used*100) / opt_memory_used;
  1046.    pl_memory = (pl_memory_used*100) / opt_memory_used;
  1047.   
  1048.  
  1049.       // Berechne die Kennzahl der Zeiteffizienz 
  1050.       // Es wird die durchschnittliche Laenge einer Seitenliste berechnet
  1051.       // Falls keine Seitenlisten existieren, so ist die Effizienz
  1052.       // optimal. Die HT-Erweiterung ist in diesem Sinne optimal, auch wenn 
  1053.       // durch fruehere Seitenlisten die Effizienz nicht 1000 entspricht, 
  1054.       // ist der einzige moegliche Weg dorthin die HT-Erweiterung.
  1055.  
  1056.    sos_Int ht_eff = 100;
  1057.    sos_Int pl_eff = 100*(no_of_pages+1)/ht_entries;
  1058.  
  1059.  
  1060.       // Jetzt kommt die Entscheidung: Beide Kennzahlen
  1061.       // werden gleich gewichtet und verglichen
  1062.    sos_Bool result = FALSE;
  1063.    if ((ht_memory + ht_eff) <= (pl_memory + pl_eff))
  1064.       result = TRUE;
  1065.  
  1066.    TT(agg_M, T_LEAVE);
  1067.    return result;
  1068. } // ** Mapping::increase_ht_structur **
  1069.  
  1070.  
  1071. // ************************************************************************** 
  1072. sos_Int neccessary_local_depth(sos_Bool      list_cursor,
  1073.                                sos_Container ct, 
  1074.                                sos_Bool      key_based_on_equal,
  1075.                                sos_Offset    page_list_offset, 
  1076.                                sos_Char      local_depth,
  1077.                                sos_Offset&   last_page_offset,
  1078.                                sos_Int       org_hash_value, 
  1079.                                sos_Object    key)
  1080. // ************************************************************************** 
  1081. // Es wird berechnet, welche lokale Tiefe eine volle Seitenliste
  1082. // plus dem einzufuegenden Objekt haben muesste, damit mindestens 
  1083. // ein Seiten Eintrag abgespalten
  1084. // werden koennte. Oder: Es wird berechnet, bis zu welchem
  1085. // Bit im Hash-Wert nicht mehr alle Seiteneintraege gleich sind
  1086. // Wird dagegen ein Eintrag gefunden, der durch den neuen Eintrag
  1087. // ersetzt wuerde, so wird dieselbe lokale Tiefe zurueckgeliefert
  1088. {  T_PROC("neccessary_local_depth");
  1089.    TT(agg_M, T_ENTER);
  1090.  
  1091.    sos_Int hash_value = org_hash_value;
  1092.    sos_Int nec_local_depth = MAX_GLOBAL_DEPTH;
  1093.    sos_Offset page_offset = page_list_offset;
  1094.  
  1095.    page_header_t first_page_header;
  1096.    first_page_header = read_page_header(ct, page_list_offset);
  1097.    sos_Int pages = first_page_header.pages;
  1098.    sos_Int entries_on_last_page = first_page_header.entries_on_last_page;
  1099.    sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  1100.       // Durchlaufe alle Seiten
  1101.    for (sos_Int page_no=1; 
  1102.         (page_no<=pages);
  1103.         page_no++)
  1104.    {     // Diese Schleife darf nicht vorher abgebrochen werden, da
  1105.          // last_page_offset als Ausgabeparameter erwartet wird
  1106.  
  1107.       page_t page;
  1108.       if (page_no == pages) 
  1109.      entries_on_page = entries_on_last_page;
  1110.       read_page(list_cursor, ct, page_offset,entries_on_page, page);
  1111.  
  1112.       last_page_offset = page_offset;
  1113.       page_offset = page.page_header.next_page;
  1114.  
  1115.          // Durchlaufe alle Eintraege auf dieser Seite
  1116.       for (sos_Int entry_no = 0;
  1117.            (entry_no < entries_on_page);
  1118.            entry_no++)
  1119.       {  sos_Int tmp_hash_value = page.entry[entry_no].hash_value;
  1120.  
  1121.          if (org_hash_value == tmp_hash_value)
  1122.          {  sos_Object o = make_Object(page.entry[entry_no].key);
  1123.             if (agg_same_entity (key, o,key_based_on_equal, EQ_STRONG))
  1124.             {     // das Objekt wuerde dieses Objekt ersetzen, also
  1125.                // keine Erhoehung der lokalen Tiefe notwendig
  1126.            TT(agg_M, T_LEAVE);
  1127.                return local_depth;
  1128.             }
  1129.          }
  1130.             // Ab dem wievielten Bit unterscheiden sich der bisherige 
  1131.             // Hashwert und der aktuelle Eintrag ?
  1132.          sos_Int diff_hash_value = hash_value BITXOR tmp_hash_value;
  1133.  
  1134.             // Die Bits der lokalen Tiefe sind auf alle Faelle gleich,
  1135.             // also rechne erst ab local_depth+1; 
  1136.          for (sos_Int i = local_depth+1; 
  1137.               i<=nec_local_depth; 
  1138.               i++)
  1139.             if ((RSHIFT(diff_hash_value, i-1) BITAND 1) == 1)
  1140.                nec_local_depth = i++;
  1141.       } 
  1142.    } 
  1143.  
  1144.    TT(agg_M, T_LEAVE);
  1145.    return nec_local_depth;
  1146. } // ** Mapping::neccessary_local_depth *
  1147.  
  1148. // insert_in_list__30_sos_Object_sos_Object_MappingR12sos_Typed_idG10sos_ObjectN32
  1149. // ************************************************************************** 
  1150. void sos_Object_sos_Object_Mapping::insert_in_list
  1151.                                        (sos_Object key, sos_Object info, 
  1152.                                         sos_Object pred, sos_Object succ)
  1153. // ************************************************************************** 
  1154. // fuegt einen Eintrag ein und setzt ihn, falls list_cursor == TRUE
  1155. // in die durch pred und succ gegebenene Reihenfolge
  1156. {  T_PROC("Mapping::insert_in_list");
  1157.    TT(agg_M, T_ENTER);
  1158.  
  1159.       // Ist das Mapping leer, so existiert noch keine Hashtabelle
  1160.    if (self.get_ht_entries() == 0)
  1161.       self.init_table();
  1162.  
  1163.    sos_Container ct            = self.container();
  1164.    sos_Bool key_based_on_equal = self.get_key_based_on_equal();
  1165.    sos_Bool list_cursor        = self.get_list_cursor();
  1166.    sos_Int org_hash_value      = absolute((key_based_on_equal)?
  1167.                                           key.hash_value():hash_id(key));
  1168.    sos_Int ht_pos              = org_hash_value MOD self.get_ht_entries();
  1169.    sos_Offset ht_offset        = self.get_ht_offset();
  1170.    ht_entry_t ht_entry         = read_ht_entry(ct,ht_offset,ht_pos);
  1171.  
  1172.    page_header_t page_header   = read_page_header(ct,ht_entry.page_list_offset);
  1173.  
  1174.       // Ist die Seitenliste aufgefuellt ?
  1175.    if (page_header.entries_on_last_page < MAX_PAGE_ENTRIES(list_cursor))
  1176.          // Nein, es ist noch Platz
  1177.       self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
  1178.                                 ht_entry.page_list_offset, org_hash_value, 
  1179.                                 key, info, pred, succ);
  1180.    else
  1181.    {     // Die Seitenliste ist voll. Entweder wird die HT erweitert,
  1182.          // oder die Seitenliste wird um eine Seite vergroessert.
  1183.       sos_Offset last_page =0;
  1184.       sos_Int nec_local_depth = 
  1185.           neccessary_local_depth( list_cursor, ct, key_based_on_equal, 
  1186.                                   ht_entry.page_list_offset, 
  1187.                                   ht_entry.local_depth,
  1188.                                   last_page, org_hash_value, key);
  1189.  
  1190.          // Falls der Eintrag einen anderen ersetzt, so 
  1191.          // ist keine Erweiterung notwendig
  1192.       if (nec_local_depth == ht_entry.local_depth)
  1193.          self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
  1194.                                    ht_entry.page_list_offset, org_hash_value, 
  1195.                                    key, info, pred, succ);
  1196.       else
  1197.       {  if (increase_ht_structur
  1198.                (list_cursor,
  1199.                 self.get_global_depth(),self.get_ht_entries(),
  1200.                 self.get_no_of_pages(),self.get_cardinality(),
  1201.                 ht_entry.local_depth, nec_local_depth))
  1202.          {     // Die Hash-Struktur wird vergroessert, erweitere 
  1203.            // zuerst die Hashtabelle auf die benoetigten Groesse
  1204.             for (;self.get_global_depth() < nec_local_depth;)
  1205.                self.increase_hash_table(); // veraendert get_global_depth() !
  1206.                // Teile jetzt die Seiten. Hierbei sind alle Seitenteilungen
  1207.                // ohne Objektumschaufelungen verbunden, bis auf die letzte.
  1208.                // Drum der Parameter nec_local_depth
  1209.             self.split_page (ct, list_cursor,
  1210.                              ht_entry.page_list_offset, ht_entry.local_depth, 
  1211.                              org_hash_value, nec_local_depth);
  1212.    
  1213.             ht_pos = org_hash_value MOD self.get_ht_entries();
  1214.             ht_entry = read_ht_entry(ct,self.get_ht_offset(), ht_pos);
  1215.             self.insert_in_page_list (ct, key_based_on_equal, list_cursor,
  1216.                                       ht_entry.page_list_offset, 
  1217.                                       org_hash_value, key, info, 
  1218.                                       pred, succ);
  1219.          }
  1220.          else
  1221.          {     // Die Seitenliste wird um eine Seite erweitert:
  1222.             increase_page_list(list_cursor, ct, ht_entry.page_list_offset,
  1223.                                page_header, last_page);
  1224.             self.set_no_of_pages(self.get_no_of_pages()+1);
  1225.  
  1226.             self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
  1227.                                      ht_entry.page_list_offset,org_hash_value,
  1228.                                      key, info, pred, succ);
  1229.          }
  1230.       }
  1231.    }
  1232.    TT (agg_M,T_LEAVE);
  1233. } // ** Mapping:insert_in_list **
  1234.  
  1235. // remove_from_page_list__30_sos_Object_sos_Object_MappingR12sos_Typed_idG13sos_Container8sos_BoolT3UiiG10sos_Object
  1236. // ************************************************************************** 
  1237. sos_Object sos_Object_sos_Object_Mapping::remove_from_page_list
  1238.                                            (sos_Container ct,
  1239.                                             sos_Bool      list_cursor,
  1240.                                             sos_Bool      key_based_on_equal,
  1241.                                             sos_Offset    page_list_offset,
  1242.                                             sos_Int       org_hash_value,
  1243.                                             sos_Object    key)
  1244. // ************************************************************************** 
  1245. // Liefert sos_Bool_Object::TRUE, falls der Eintrag gefunden wurde. Der Entry
  1246. // wird nicht geliefert, da er sonst mit make_Object angefasst werden muesste, 
  1247. // was er hier nicht soll.
  1248. {  T_PROC("Mapping::remove_from_page_list");
  1249.    TT(agg_M, T_ENTER);
  1250.  
  1251.    sos_Object my_no_object = self;
  1252.       // assume that key won't be found:
  1253.    sos_Object  found = make_sos_Bool_object(FALSE); 
  1254.    page_t page;
  1255.    page_header_t page_header;
  1256.    sos_Offset page_offset = page_list_offset;
  1257.    sos_Offset prev_page_offset;
  1258.    page_header = read_page_header(ct, page_offset);
  1259.    sos_Int pages = page_header.pages;
  1260.    sos_Int entries_on_last_page = page_header.entries_on_last_page;
  1261.    sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  1262.    sos_Int page_no = 1;
  1263.    sos_Int pos = -1; // entspricht "nicht gefunden";
  1264.    for (; (page_no<=pages) AND (pos == -1); page_no++)
  1265.    {  if (page_no == pages)
  1266.      entries_on_page = entries_on_last_page;
  1267.       read_page(list_cursor, ct, page_offset, entries_on_page, page);
  1268.       pos = search_page_for_key (key_based_on_equal, page, 
  1269.                                  entries_on_page, 
  1270.                                  org_hash_value,key);
  1271.       if (pos == -1)
  1272.       {  prev_page_offset  = page_offset;
  1273.          page_offset = page.page_header.next_page;
  1274.       }
  1275.    } 
  1276.    
  1277.    page_no --;
  1278.       // Im Falle von based_on_equal == TRUE ist der key nicht unbedingt 
  1279.       // derselbe wie der tatsaechlich eingetragene Schluessel. real_key
  1280.       // ist der Eingetragene. real_key ist fuer den Test auf Identitaet
  1281.       // mit dem ersten bzw. letzten Element notwendig.(Equal ginge auch,
  1282.       // dauert aber laenger).
  1283.    sos_Object real_key;  
  1284.  
  1285.    if (pos != -1)
  1286.    {  found = make_sos_Bool_object(TRUE);
  1287.       real_key = make_Object(page.entry[pos].key);
  1288.  
  1289.       sos_Object pred,succ;
  1290.       if (list_cursor)
  1291.       {  pred = make_Object(page.list[pos].pred);
  1292.          succ = make_Object(page.list[pos].succ);
  1293.       }
  1294.       self.set_cardinality(self.get_cardinality() - 1);
  1295.  
  1296.          // Der zu loeschende Eintrag ist auf der letzten Seite 
  1297.       if (page_no == page_header.pages)
  1298.       {     // fuelle die Luecke auf
  1299.          if (page_header.entries_on_last_page > 1)
  1300.          {     // und korrigiere den Seitenheader
  1301.             page.entry[pos] = page.entry[--page_header.entries_on_last_page];
  1302.             page.list[pos]  = page.list[page_header.entries_on_last_page];
  1303.                // schreibe Seiteneintrag zurueck
  1304.             write_page_entry(list_cursor, ct, page_offset, pos, page);
  1305.          }
  1306.          else
  1307.             // oder deallokiere die Seite
  1308.          {  if (page_header.pages > 1)
  1309.             {  ct.deallocate(page_offset, PAGE_SIZE(list_cursor));
  1310.                page_header.pages --;
  1311.                page_header.entries_on_last_page=MAX_PAGE_ENTRIES(list_cursor);
  1312.                self.set_no_of_pages(self.get_no_of_pages()-1);
  1313.             }
  1314.             else
  1315.                page_header.entries_on_last_page = 0;
  1316.         }
  1317.             // schreibe Seitenheader zurueck
  1318.          write_page_header(ct,page_list_offset, page_header);
  1319.       }
  1320.       else
  1321.       {     // Falls der Eintrag nicht auf der letzten Seite war, so nimm
  1322.             // einen Eintrag der letzten Seite und schreibe ihn in die Luecke
  1323.             // hangel dich zur letzten Seite vor
  1324.          sos_Offset last_page_offset = page.page_header.next_page;
  1325.          page_header_t tmp_page_header;
  1326.          page_no++;
  1327.          for (;page_no<page_header.pages;page_no++)
  1328.          {  tmp_page_header = read_page_header(ct, last_page_offset);
  1329.             last_page_offset = tmp_page_header.next_page;
  1330.          } 
  1331.  
  1332.             // nimm von der letzten Seite den letzten Eintrag
  1333.             // und korrigiere nur den Seitenheader
  1334.          page_t tmp_page;
  1335.          read_page_entry(list_cursor, ct,last_page_offset, 
  1336.                          --page_header.entries_on_last_page,
  1337.                          tmp_page);
  1338.  
  1339.             // und fuege ihn in die Luecke
  1340.          page.entry[pos] = tmp_page.entry[page_header.entries_on_last_page];
  1341.          page.list[pos]  = tmp_page.list[page_header.entries_on_last_page];
  1342.  
  1343.          write_page(list_cursor, ct,page_offset, pos+1, page);
  1344.  
  1345.             // Falls die letzte Seite jetzt leer ist, deallokiere
  1346.          if (page_header.entries_on_last_page == 0)
  1347.          {  ct.deallocate(last_page_offset, PAGE_SIZE(list_cursor));
  1348.             page_header.entries_on_last_page = MAX_PAGE_ENTRIES(list_cursor);
  1349.             page_header.pages--;
  1350.             self.set_no_of_pages(self.get_no_of_pages()-1);
  1351.          }
  1352.  
  1353.             // Schreibe den Seitenheader der ersten Seite zurueck
  1354.          write_page_header(ct,page_list_offset, page_header);
  1355.       }
  1356.      
  1357.       if (list_cursor)
  1358.       {     // fuege Objekt aus der Liste
  1359.          self.write_succ_pred
  1360.             (ct, key_based_on_equal, list_cursor, pred, TRUE, succ);
  1361.          self.write_succ_pred
  1362.             (ct, key_based_on_equal, list_cursor, succ, FALSE, pred);
  1363.       
  1364.          if (real_key == self.get_last_object())
  1365.             self.set_last_object(pred);
  1366.          if (real_key == self.get_first_object())
  1367.             self.set_first_object(succ);
  1368.             
  1369.             // Letztes Objekt:
  1370.          if (self.get_cardinality() == 0)
  1371.          {  sos_Object my_no_object = self;
  1372.             self.set_first_object(my_no_object);
  1373.             self.set_last_object(my_no_object);
  1374.          }
  1375.       }
  1376.    } 
  1377.  
  1378.    TT(agg_M, T_LEAVE);
  1379.    return found;
  1380. } // ** Mapping::remove_from_page_list **
  1381.  
  1382.  
  1383.  
  1384. // ************************************************************************** 
  1385. sos_Bool sos_Object_sos_Object_Mapping::assemble_page(
  1386.                                            sos_Offset page_list_offset,
  1387.                                            sos_Char   local_depth,
  1388.                                            sos_Int    org_hash_value)
  1389. // ************************************************************************** 
  1390. {  T_PROC("Mapping::assemble_page");
  1391.    TT(agg_M, T_ENTER);
  1392.  
  1393.    sos_Container ct         = self.container(); 
  1394.    sos_Bool list_cursor     = self.get_list_cursor();
  1395.    sos_Int max_page_entries = MAX_PAGE_ENTRIES(list_cursor);
  1396.  
  1397.    page_t page;
  1398.    page_t partner_page;
  1399.    ht_entry_t ht_partner_entry;
  1400.  
  1401.    page.page_header     = read_page_header(ct, page_list_offset);
  1402.    sos_Int ht_partner_pos;
  1403.  
  1404.    sos_Bool assemble_flag;
  1405.       // liefere zurueck, ob verschmolzen wurde
  1406.    sos_Bool result             = FALSE; 
  1407.    sos_Bool act_page_is_read   = FALSE;
  1408.  
  1409.    do // while (assemble_flag)
  1410.    {  assemble_flag = FALSE;
  1411.  
  1412.          // zuerst eine Grob-Pruefung, ob eine Chance auf 
  1413.          // Verschmelzung besteht:
  1414.          // Ist die Seitenliste nur eine Seite, und ist sie nur 3/4 voll,
  1415.          // und gibt es ueberhaupt eine Partnerseite ?
  1416.       if ((page.page_header.entries_on_last_page <= max_page_entries*3/4) AND
  1417.           (page.page_header.pages == 1) AND
  1418.           (local_depth > 0))
  1419.       {     // Berechne die Position der Partnerseite
  1420.          ht_partner_pos     = (org_hash_value BITAND LSHIFT(1,local_depth)-1)
  1421.                               BITXOR LSHIFT(1,local_depth-1);
  1422.  
  1423.             // Lese den HT-Eintrag der Partnerseite
  1424.          ht_partner_entry =
  1425.             read_ht_entry(ct,self.get_ht_offset(),ht_partner_pos);
  1426.          
  1427.             // Hat die Partnerseite die gleiche lokale Tiefe ?
  1428.          if (ht_partner_entry.local_depth == local_depth)
  1429.          {     // Ja
  1430.                // Lese Seitenkopf der Partner Seite
  1431.             partner_page.page_header = 
  1432.                    read_page_header(ct, ht_partner_entry.page_list_offset);
  1433.             
  1434.                // Besteht die Partnerseite auch nur aus einer Seite ?
  1435.             if (partner_page.page_header.pages == 1)
  1436.             {  // passen alle Eintraege gut auf eine Seite ? (gut = 25% frei)
  1437.                assemble_flag = FALSE;
  1438.                if ((partner_page.page_header.entries_on_last_page+
  1439.                      page.page_header.entries_on_last_page)
  1440.                      <= max_page_entries*3/4)
  1441.                   assemble_flag = TRUE;
  1442.             }
  1443.          } 
  1444.       }
  1445.  
  1446.       if (assemble_flag) 
  1447.       {  result = TRUE;
  1448.  
  1449.          self.set_no_of_page_lists(self.get_no_of_page_lists() - 1);
  1450.  
  1451.          if (NOT (act_page_is_read))
  1452.          {  read_page(list_cursor, ct,page_list_offset, 
  1453.                       page.page_header.entries_on_last_page, page);
  1454.             act_page_is_read = TRUE;
  1455.          }
  1456.  
  1457.             // Lese Partner-Seite
  1458.          read_page(list_cursor, ct,ht_partner_entry.page_list_offset, 
  1459.                    partner_page.page_header.entries_on_last_page, 
  1460.                    partner_page);
  1461.  
  1462.             // Kopiere die Eintraege der Partnerseite 
  1463.             // auf die urspruengliche Seite
  1464.          for (sos_Int i=0; i<partner_page.page_header.entries_on_last_page;i++)
  1465.          {  page.entry[page.page_header.entries_on_last_page] = 
  1466.                partner_page.entry[i];
  1467.             page.list[page.page_header.entries_on_last_page++] = 
  1468.                partner_page.list[i];
  1469.          } 
  1470.  
  1471.             // Korrigiere die Angabe, wieviel Seiten mit einer 
  1472.             // bestimmten lokalen Tiefe existieren
  1473.          sos_Int no_of_pages_offset = self.get_no_of_pages_offset();
  1474.          add_no_of_pages(ct,no_of_pages_offset,local_depth,-2);
  1475.          add_no_of_pages(ct,no_of_pages_offset,local_depth-1,1);
  1476.  
  1477.             // Gib die Partnerseite frei
  1478.          ct.deallocate (ht_partner_entry.page_list_offset, 
  1479.                         PAGE_SIZE(list_cursor));
  1480.          self.set_no_of_pages(self.get_no_of_pages()-1);
  1481.  
  1482.          write_page(list_cursor, ct,page_list_offset, 
  1483.                     page.page_header.entries_on_last_page, page);
  1484.        
  1485.          sos_Int old_local_depth = local_depth --;
  1486.  
  1487.             // Die Hashtabelle muss korrigiert werden: Alle
  1488.             // Verweise auf die Partnerseite muessen auf die verschmolzene
  1489.             // Seite umgebogen werden
  1490.             // Wie lautet der der vereinigten Seite zugeordnete Hashwertteil ? 
  1491.          sos_Int hash_value_part = ht_partner_pos BITAND 
  1492.                                (LSHIFT(1,local_depth)-1);
  1493.  
  1494.             // Laufe alle Indexe durch, die auf die neue
  1495.             // vereinigte Seite zeigen. Diese Verweise werden
  1496.             // umgebogen
  1497.          sos_Int global_depth = self.get_global_depth();
  1498.          sos_Offset ht_offset = self.get_ht_offset();
  1499.          for (sos_Int k = 0;k<LSHIFT(1,global_depth-local_depth); k++)
  1500.          {     // verschiebe Laufindex k an richtige Position 
  1501.                // vor dem Wert der Seite
  1502.             sos_Int j = LSHIFT(k,local_depth);
  1503.                // addiere hash-Teil der Seite dazu
  1504.             j = j BITOR hash_value_part;
  1505.             
  1506.                // Dieser Eintrag muss auf die neue Seite umgebogen werden
  1507.                // d.h. vielleicht zeigt er schon auf die Seite, aber
  1508.                // die lokale Tiefe ist in jedem Fall zu hoch
  1509.             ht_entry_t ht_entry;
  1510.             ht_entry.page_list_offset = page_list_offset;
  1511.             ht_entry.local_depth = local_depth;
  1512.             write_ht_entry(ct,ht_offset,j, ht_entry);
  1513.          }
  1514.       }
  1515.    } 
  1516.    while (assemble_flag);
  1517.  
  1518.    TT(agg_M,T_LEAVE);
  1519.    return result;
  1520. } // ** Mapping::assemble_page **
  1521.  
  1522.  
  1523. // ************************************************************************** 
  1524. void sos_Object_sos_Object_Mapping::decrease_hash_table()
  1525. // ************************************************************************** 
  1526. // die Hash-tabelle kann genau dann halbiert werden, wenn
  1527. // keine Seiten existieren, die nur einen Verweis in der 
  1528. // Hash-Tabelle besitzen
  1529. {  
  1530.    T_PROC("Mapping::decrease_hash_table");
  1531.    TT(agg_M, T_ENTER);
  1532.  
  1533.    sos_Container ct              = self.container(); 
  1534.    sos_Int global_depth          = self.get_global_depth();
  1535.    sos_Offset no_of_pages_offset = self.get_no_of_pages_offset();
  1536.  
  1537.    for (;no_single_referenced_pages(ct,no_of_pages_offset,global_depth);)
  1538.    {     // Merke alte Tabellen-Position und Laenge
  1539.       sos_Int old_ht_entries   = self.get_ht_entries();
  1540.       sos_Int old_ht_size      = old_ht_entries*HT_ENTRY_SIZE;
  1541.       sos_Offset old_ht_offset = self.get_ht_offset();
  1542.  
  1543.          // definiere neue Tabellen Position und Laenge
  1544.       sos_Int new_ht_entries = old_ht_entries / 2;
  1545.       sos_Int new_ht_size   = new_ht_entries*HT_ENTRY_SIZE;
  1546.       sos_Int new_ht_offset = ct.allocate(new_ht_entries*HT_ENTRY_SIZE);
  1547.       self.set_ht_entries(new_ht_entries);
  1548.       self.set_ht_offset(new_ht_offset);
  1549.  
  1550.          // kopiere erste Haelfte der alten Tabelle in neue Tabelle
  1551.       ct.copy( old_ht_offset,new_ht_size,ct,new_ht_offset); 
  1552.       global_depth--;
  1553.       
  1554.          // Gib alte Tabelle frei
  1555.       ct.deallocate(old_ht_offset,old_ht_size);
  1556.    }
  1557.    self.set_global_depth(global_depth);
  1558.    TT (agg_M,T_LEAVE); 
  1559. } // ** decrease_hash_table
  1560.  
  1561. // ************************************************************************** 
  1562. sos_Bool get_entry (sos_Container  ct, 
  1563.                     sos_Bool       list_cursor,
  1564.                     sos_Bool       key_based_on_equal, 
  1565.                     sos_Int        ht_entries,
  1566.                     sos_Offset     ht_offset,
  1567.                     sos_Object&    key,
  1568.             sos_Bool       return_info,
  1569.             sos_Object&    info,
  1570.                     sos_Object&    pred,
  1571.                     sos_Object&    succ)
  1572. // ************************************************************************** 
  1573. // Setzt key und - falls list_cursor == TRUE - pred und succ auf die
  1574. // key-Objekte im gegebenen Mapping. Ergebnis ist das dem key entsprechende
  1575. // info. Es gilt agg_same_entity (key-vorher, key-nachher, key_based_on_equal)
  1576. // Wird return_info== TRUE uebergeben, wird info geliefert, ansonsten nicht.
  1577. // pred und succ werden nur im Falle von list_cursor == TRUE geliefert.
  1578.     
  1579. {  T_PROC("get_entry");
  1580.    TT(agg_M,T_ENTER; TI(ht_entries); TI(ht_offset));
  1581.  
  1582.    if (ht_entries>0)
  1583.    {  sos_Int org_hash_value  = absolute((key_based_on_equal)?
  1584.                                          key.hash_value() : hash_id(key));
  1585.       sos_Int ht_pos          = org_hash_value MOD ht_entries;
  1586.       ht_entry_t ht_entry     = read_ht_entry(ct,ht_offset,ht_pos);
  1587.       page_t page;
  1588.  
  1589.       sos_Offset page_offset  = ht_entry.page_list_offset;
  1590.       sos_Int pos = -1; // entspricht "nicht gefunden"
  1591.  
  1592.       page_header_t page_header = read_page_header (ct, page_offset);
  1593.       sos_Int pages = page_header.pages;
  1594.       sos_Int entries_on_last_page = page_header.entries_on_last_page;
  1595.       sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  1596.       for (sos_Int page_no = 1; (page_no<=pages) AND (pos == -1); page_no++)
  1597.       {  if (page_no == pages)
  1598.         entries_on_page = entries_on_last_page;
  1599.          
  1600.          read_page(list_cursor, ct, page_offset, entries_on_page, page);
  1601.          pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
  1602.                                      org_hash_value, key );
  1603.          if (pos == -1)
  1604.             page_offset = page.page_header.next_page;
  1605.          else
  1606.          {  if (list_cursor)
  1607.             {  pred = make_Object(page.list[pos].pred);
  1608.                succ = make_Object(page.list[pos].succ);
  1609.            sos_Bool test1 = (succ == NO_OBJECT);
  1610.            sos_Bool test2 = (pred == NO_OBJECT);
  1611.             }
  1612.             key = make_Object(page.entry[pos].key);
  1613.             if (return_info)
  1614.            info = make_Object(page.entry[pos].info);
  1615.          
  1616.             TT(agg_M, T_LEAVE);
  1617.            // gefunden !
  1618.             return TRUE;
  1619.          }
  1620.       } 
  1621.    }   
  1622.    TT(agg_M,T_LEAVE);
  1623.       // nicht gefunden:
  1624.    return FALSE;
  1625. } // ** get_entry **
  1626.  
  1627. /*
  1628. Reihenfolge in der Hashtabelle:
  1629. Die Ordnung bezieht sich immer nur auf diejenigen Verweise in der Hashtabelle,
  1630. die die ersten Verweise auf eine bestimmte Seitenliste sind. Das Durchlaufen
  1631. mit einem Cursor funktioniert auf der Version mit list_cursor == FALSE so:
  1632. Die Cursor-Operatoren wurden ueberlagert, mit dem Oeffnen eines Cursors werden
  1633. die Prozeduren read_first_object und read_last_object aufgerufen, die das 
  1634. erste und letzte Objekt liefern. open_cursor setzt nun die Variablen 
  1635. first_object und last_object.  Beim Durchlaufen mit dem Cursor wird die 
  1636. Hashtabelle solange durchsucht, bis ein Verweis gefunden wird, der der Erste
  1637. auf die referenzierte Seitenliste ist. Dies ist der Fall, wenn in der Position
  1638. der Hashtabelle (ht_pos) nur die ersten (lokale_tiefe) Bit gesetzt sind. Auf 
  1639. der Seitenliste werden die Eintraege gemaess der Reihenfolge auf der Seite 
  1640. durchlaufen. Nach dem letzten Eintrag auf der Seitenliste beginnt wieder die
  1641. Suche in der Hashtabelle nach einem ersten Verweis auf die naechste 
  1642. Seitenliste.
  1643. */
  1644.  
  1645. // ************************************************************************** 
  1646. sos_Object get_pred ( sos_Container  ct,
  1647.                       sos_Bool       key_based_on_equal,
  1648.                       sos_Object     my_no_object,
  1649.                       sos_Int        ht_entries,
  1650.                       sos_Offset     ht_offset,
  1651.                       sos_Object     key)
  1652. // ************************************************************************** 
  1653. // Diese Prozedur wird nur aufgerufen, wenn get_list_cursor() == FALSE,
  1654. // d.h. die Version ohne verkettung der Eintraege ist gefragt.
  1655. // Es wird das Objekt in der eben geschilderten Reihenfolge nach key 
  1656. // geliefert.
  1657. {  sos_Int org_hash_value  =absolute((key_based_on_equal)?
  1658.                                       key.hash_value() : hash_id(key));
  1659.    sos_Int ht_pos = org_hash_value MOD ht_entries;
  1660.    sos_Object result;
  1661.  
  1662.    ht_entry_t ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1663.    page_t page;
  1664.    sos_Int first_link = FIRST_LINK(ht_pos, ht_entry.local_depth);
  1665.    ht_pos = first_link;
  1666.    sos_Offset page_offset = ht_entry.page_list_offset;
  1667.  
  1668.    page_header_t page_header = read_page_header (ct, page_offset);
  1669.    sos_Int pages = page_header.pages;
  1670.    sos_Int entries_on_last_page = page_header.entries_on_last_page;
  1671.    sos_Int entries_on_page = max_page_entries_without_list;
  1672.    result = my_no_object;
  1673.    sos_Int pos = -1; // entspricht "nicht gefunden"
  1674.    for (sos_Int page_no = 1;
  1675.         (page_no<=pages) AND (pos == -1);
  1676.         page_no++)
  1677.    {  if (page_no == pages)
  1678.      entries_on_page = entries_on_last_page;
  1679.  
  1680.       read_page(FALSE, ct, page_offset, entries_on_page, page);
  1681.       pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
  1682.                                   org_hash_value, key );
  1683.       if (pos == -1)
  1684.       {  page_offset = page.page_header.next_page;
  1685.          result = make_Object(page.entry[entries_on_page-1].key);
  1686.       }
  1687.       else
  1688.       {     // Findet sich der Vorgaenger auf derselben Seite ?
  1689.          if (pos > 0)
  1690.             result = make_Object(page.entry[pos-1].key);
  1691.          else
  1692.          {     // Falls eine vorherige Seite in der seitenliste
  1693.                // existiert, so wurde ihr letzter Eintrag in
  1694.                // result bereits gesetzt. Ist es jedoch die erste Seite
  1695.                // muss auf eine vorherige Seitenliste gegangen werden
  1696.             if (page_no == 1)
  1697.             {  sos_Bool found = FALSE;
  1698.                do
  1699.                {  ht_pos--;
  1700.                   do
  1701.                   {  if (ht_pos >= 0)
  1702.                      {     // suche den naechsten ersten verweis ab ht_pos;
  1703.                         ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1704.                         first_link = FIRST_LINK(ht_pos, ht_entry.local_depth);
  1705.  
  1706.                         if (first_link != ht_pos)
  1707.                            ht_pos--;
  1708.                       }
  1709.                   } while ((first_link != ht_pos) AND (ht_pos >= 0));
  1710.  
  1711.                   if (ht_pos >= 0)
  1712.                   {  page_header = 
  1713.                        read_page_header(ct,ht_entry.page_list_offset);
  1714.  
  1715.                         // Falls auf dieser Seitenliste ein
  1716.                         // Eintrag ist, lese ihn, sonst bleibt found == FALSE
  1717.                      if ((page_header.pages > 1) OR
  1718.                          (page_header.entries_on_last_page > 0))
  1719.                      {  found = TRUE;
  1720.                            // lese letzte Seite
  1721.                         sos_Int i = read_page(FALSE, ct,page_header, ht_entry,
  1722.                                           page_header.pages, page);
  1723.                         result = make_Object(page.entry[i-1].key);
  1724.                      }
  1725.                   }
  1726.                } while ((NOT found) AND (ht_pos >= 0));
  1727.             }
  1728.          }
  1729.       }
  1730.    } 
  1731.  
  1732.    return result;
  1733. } // ** get_pred **
  1734.  
  1735. // ************************************************************************** 
  1736. sos_Object get_succ ( sos_Container  ct,
  1737.                       sos_Bool       key_based_on_equal,
  1738.                       sos_Object     my_no_object,
  1739.                       sos_Int        ht_entries,
  1740.                       sos_Offset     ht_offset,
  1741.                       sos_Object     key)
  1742. // ************************************************************************** 
  1743. {  sos_Int org_hash_value = absolute((key_based_on_equal)?
  1744.                                      key.hash_value() : hash_id(key));
  1745.    sos_Int ht_pos = org_hash_value MOD ht_entries;
  1746.    sos_Object result;
  1747.  
  1748.    ht_entry_t ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1749.    page_t page;
  1750.    sos_Int first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
  1751.    ht_pos = first_link;
  1752.    sos_Offset page_offset = ht_entry.page_list_offset;
  1753.  
  1754.    page_header_t page_header = read_page_header (ct, page_offset);
  1755.    sos_Int pages = page_header.pages;
  1756.    sos_Int entries_on_last_page = page_header.entries_on_last_page;
  1757.    sos_Int entries_on_page = max_page_entries_without_list;
  1758.    result = my_no_object;
  1759.    sos_Int pos = -1; // entspricht "nicht gefunden"
  1760.    for (sos_Int page_no = 1; (page_no<=pages) AND (pos == -1); page_no++)
  1761.    {  if (page_no == pages)
  1762.      entries_on_page = entries_on_last_page;
  1763.  
  1764.       read_page(FALSE, ct, page_offset, entries_on_page, page);
  1765.       pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
  1766.                                   org_hash_value, key );
  1767.       if (pos == -1)
  1768.          page_offset = page.page_header.next_page;
  1769.       else
  1770.       {     // Findet sich der Nachfolger auf derselben Seite ?
  1771.          if (pos < entries_on_page-1)
  1772.             result = make_Object(page.entry[pos+1].key);
  1773.          else
  1774.          {  if (page_no < page_header.pages)
  1775.             {  read_page(FALSE, ct, page.page_header.next_page, 1, page);
  1776.                result = make_Object(page.entry[0].key);
  1777.             }
  1778.             else
  1779.             {     // Der Schluessel ist der letzte Eintrag auf der 
  1780.                   // Seitenliste, der Nachfolger ist auf der 
  1781.                   // naechsten Seitenliste
  1782.                sos_Bool found = FALSE;
  1783.                do
  1784.                {  ht_pos++;
  1785.                   do
  1786.                   {     // suche den naechsten ersten verweis ab ht_pos;
  1787.                         // read ht_entry
  1788.                      if (ht_pos < ht_entries)
  1789.                      {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1790.                         first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
  1791.                         if (first_link != ht_pos)
  1792.                            ht_pos++;
  1793.                      }
  1794.                    } while ((first_link != ht_pos) AND (ht_pos < ht_entries));
  1795.                       
  1796.                    if (ht_pos < ht_entries)
  1797.                    {     // lese den Seitenkopf und das erste 
  1798.                          // Objekt dieser Seite
  1799.                       read_page(FALSE,ct, ht_entry.page_list_offset, 1, page);
  1800.                       if ((page.page_header.pages > 1) OR
  1801.                           (page.page_header.entries_on_last_page > 0))
  1802.                       {  found = TRUE;
  1803.                          result = make_Object(page.entry[0].key);
  1804.                       }
  1805.                   }
  1806.                } while ((NOT found) AND (ht_pos < ht_entries));
  1807.             }
  1808.          }
  1809.       }
  1810.    } 
  1811.  
  1812.    return result;
  1813. } // ** Mapping::get_succ **
  1814.  
  1815.  
  1816. // ************************************************************************** 
  1817. sos_Object sos_Object_sos_Object_Mapping::search_succ_pred
  1818.                                              (sos_Object key, sos_Int steps)
  1819. // ************************************************************************** 
  1820. {  T_PROC("Mapping::search_succ_pred");
  1821.    TT(agg_M, T_ENTER; TI (steps));
  1822.  
  1823.    sos_Container ct             = self.container();
  1824.    sos_Bool key_based_on_equal  = self.get_key_based_on_equal();
  1825.    sos_Bool list_cursor         = self.get_list_cursor();
  1826.    sos_Object my_no_object      = self;
  1827.    sos_Int ht_entries           = self.get_ht_entries();
  1828.    sos_Offset ht_offset         = self.get_ht_offset();
  1829.    sos_Object dummy_info;  // wird in get_entry nicht angefasst
  1830.  
  1831.    for (;steps != 0;)
  1832.    {  sos_Object pred,succ;
  1833.       if (list_cursor)
  1834.       {  get_entry(ct, list_cursor, key_based_on_equal,
  1835.                    ht_entries,ht_offset, 
  1836.                    key, FALSE, dummy_info, pred,succ);
  1837.          if (steps > 0)
  1838.          {  if (succ == my_no_object)
  1839.         {  TT(agg_M, T_LEAVE);
  1840.                return my_no_object;
  1841.             }
  1842.             key = succ;
  1843.             steps--;
  1844.          }
  1845.          else
  1846.          {  if (pred == my_no_object)
  1847.         {  TT(agg_M, T_LEAVE);
  1848.                return my_no_object;
  1849.             }
  1850.             key = pred;
  1851.             steps++;
  1852.          }
  1853.       }
  1854.       else
  1855.       {  if (steps > 0)
  1856.          {  succ = get_succ(ct,key_based_on_equal,my_no_object,
  1857.                             ht_entries,ht_offset,key);
  1858.             if (succ == my_no_object)
  1859.         {  TT(agg_M, T_LEAVE);
  1860.                return my_no_object;
  1861.             } 
  1862.             key = succ;
  1863.             steps--;
  1864.          }
  1865.          else
  1866.          {  pred = get_pred(ct,key_based_on_equal,my_no_object,
  1867.                             ht_entries,ht_offset,key);
  1868.             if (pred == my_no_object)
  1869.             {  TT(agg_M, T_LEAVE);
  1870.            return my_no_object;
  1871.             }
  1872.             key = pred;
  1873.             steps++;
  1874.          }
  1875.       } 
  1876.    }
  1877.    TT(agg_M,T_LEAVE);
  1878.    return key;
  1879. } // ** Mapping::search_succ_pred **
  1880.  
  1881.  
  1882. // ************************************************************************** 
  1883. sos_Object read_last_object(sos_Container ct,
  1884.                             sos_Offset    ht_offset,
  1885.                             sos_Int       length,
  1886.                             sos_Object    my_no_object,
  1887.                             sos_Int       ht_entries)
  1888. // ************************************************************************** 
  1889. {  sos_Int ht_pos = ht_entries-1;
  1890.    sos_Bool found = FALSE;
  1891.    if (length == 0)
  1892.        return my_no_object;
  1893.    sos_Object result;
  1894.    ht_entry_t ht_entry;
  1895.    page_t page;
  1896.    page_header_t page_header;
  1897.    sos_Int first_link;
  1898.    do
  1899.    {  do
  1900.       {     // suche den vorherigen ersten Verweis ab ht_pos rueckwaerts
  1901.          ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1902.          first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
  1903.          if (first_link != ht_pos)
  1904.              ht_pos--;
  1905.       } while (first_link != ht_pos);
  1906.  
  1907.          // lese den page_header um festzustellen, ob auf der
  1908.          // Seitenliste ein Objekt ist
  1909.       page_header = read_page_header(ct,ht_entry.page_list_offset);
  1910.       if ((page_header.pages > 1) OR
  1911.           (page_header.entries_on_last_page > 0))
  1912.       {  found = TRUE;
  1913.             // lese letzte Seite
  1914.          read_page(FALSE,ct ,page_header, ht_entry, page_header.pages, page);
  1915.          result=make_Object(page.entry[page_header.entries_on_last_page-1].key);
  1916.       }
  1917.       else
  1918.          ht_pos--;
  1919.    } while (NOT found);
  1920.  
  1921.    return result;
  1922. } // ** Mapping::read_last_object **
  1923.  
  1924. // ************************************************************************** 
  1925. sos_Object read_first_object(sos_Container ct,
  1926.                              sos_Offset    ht_offset,
  1927.                              sos_Int       length,
  1928.                              sos_Object    my_no_object)
  1929. // ************************************************************************** 
  1930. {   sos_Int ht_pos = 0;
  1931.     sos_Bool found = FALSE;
  1932.     if (length == 0)
  1933.        return my_no_object;
  1934.     sos_Object result;
  1935.     ht_entry_t ht_entry;
  1936.     page_t page;
  1937.     sos_Int first_link;
  1938.  
  1939.     do
  1940.     {  do
  1941.        {     // suche den naechsten ersten verweis ab ht_pos;
  1942.              // read ht_entry
  1943.           ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1944.           first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
  1945.           if (first_link != ht_pos)
  1946.              ht_pos++;
  1947.        }
  1948.        while (first_link != ht_pos);
  1949.         
  1950.        // lese die Seite und das erste Objekt von diesem Verweis
  1951.        read_page(FALSE, ct, ht_entry.page_list_offset, 1, page);
  1952.        if ((page.page_header.pages > 1) OR
  1953.            (page.page_header.entries_on_last_page > 0))
  1954.        {  found = TRUE;
  1955.           result = make_Object(page.entry[0].key);
  1956.        }
  1957.        else
  1958.           ht_pos++;
  1959.     } while (NOT found);
  1960.     return result;
  1961. } // ** Mapping::read_first_object **
  1962.  
  1963.  
  1964. // ************************************************************************** 
  1965. void destroy_ht (sos_Bool       list_cursor,
  1966.                  sos_Container  ct, 
  1967.                  sos_Int        ht_entries, 
  1968.                  sos_Int        global_depth,
  1969.                  sos_Offset     ht_offset)
  1970. // ************************************************************************** 
  1971. {  T_PROC("destroy_ht ");
  1972.    TT (agg_M, T_ENTER; TI(ht_entries); TI(global_depth));
  1973.       // loescht alle Eintrage und die Hashtabelle,
  1974.  
  1975.    ht_entry_t ht_entry;
  1976.  
  1977.    for (sos_Int ht_pos=0;ht_pos < ht_entries;ht_pos++)
  1978.    {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  1979.       sos_Int local_depth = ht_entry.local_depth;
  1980.          // Berechne denjenigen Teil des Hashwertes, der auf der
  1981.          // Seitenliste unterschieden wird, dies ist gleichzeitig
  1982.          // der erste Verweis auf die Seitenliste
  1983.       sos_Int hash_value_part = FIRST_LINK(ht_pos, local_depth);
  1984.  
  1985.          // Berechne den letzten Verweis auf diese Seiteliste
  1986.       sos_Int last_link = LSHIFT(LSHIFT(1,global_depth-local_depth)-1,
  1987.                              local_depth) BITAND hash_value_part;
  1988.          // es muss der letzte Verweis sein, andernfalls wuerde die Kiste
  1989.          // beim nachfolgenden Lesen der lokalen Tiefe abschmieren,
  1990.          // da die Seite schon deallokiert waere.
  1991.  
  1992.          // Falls der gefundendene Verweis der letzte auf diese Seitenliste
  1993.          // ist, so deallokiere diese
  1994.       if (last_link == ht_pos) 
  1995.       {  page_header_t page_header = 
  1996.              read_page_header(ct,ht_entry.page_list_offset);
  1997.          destroy_page_list(list_cursor, ct,
  1998.                            ht_entry.page_list_offset, page_header.pages);
  1999.       }
  2000.    } 
  2001.  
  2002.    if (ht_entries>0)
  2003.       ct.deallocate(ht_offset,ht_entries*HT_ENTRY_SIZE);
  2004.  
  2005.    TT(agg_M,T_LEAVE);
  2006. } // ** Mapping::destroy_ht **
  2007.  
  2008. // ************************************************************************** 
  2009. void sos_Object_sos_Object_Mapping::init_table ()
  2010. // ************************************************************************** 
  2011. {  T_PROC("Mapping::init_table");
  2012.    TT(agg_H, T_ENTER);
  2013.  
  2014.       // create a hash-tab
  2015.       // Ein Eintrag besteht aus einem Offset
  2016.       // also einem Zeiger auf eine Seite
  2017.    self.set_ht_entries(1);
  2018.    sos_Container ct  = self.container();
  2019.    self.set_ht_offset(ct.allocate (self.get_ht_entries()*HT_ENTRY_SIZE)); 
  2020.  
  2021.       // no_of_pages[i] gibt an, wieviel Seiten mit der lokalen
  2022.       // Tiefe i existieren 
  2023.    self.set_no_of_pages_offset(ct.allocate(NO_OF_PAGES_ARRAY_SIZE));
  2024.    sos_Char mem [NO_OF_PAGES_ARRAY_SIZE];
  2025.    for (sos_Int i = 0;i< NO_OF_PAGES_ARRAY_SIZE;i++) mem[i] = 0;
  2026.    ct.write(self.get_no_of_pages_offset(), NO_OF_PAGES_ARRAY_SIZE, &mem);
  2027.  
  2028.    ht_entry_t ht_entry;
  2029.    ht_entry.page_list_offset = ct.allocate(PAGE_SIZE(self.get_list_cursor()));
  2030.    ht_entry.local_depth = 0;
  2031.    write_ht_entry(ct, self.get_ht_offset(),0,ht_entry);
  2032.  
  2033.    page_header_t page_header;
  2034.    page_header.pages = 1;
  2035.    page_header.entries_on_last_page = 0;
  2036.    write_page_header(ct,ht_entry.page_list_offset,page_header);
  2037.  
  2038.    self.set_no_of_pages(1);
  2039.    self.set_no_of_page_lists(1);
  2040.    add_no_of_pages(ct,self.get_no_of_pages_offset(),0,1);
  2041.  
  2042.    TT(agg_H,T_LEAVE);
  2043. } // ** Mapping::init_table **
  2044.  
  2045. // ************************************************************************** 
  2046. void sos_Object_sos_Object_Mapping::local_initialize
  2047.                                        (sos_Object_sos_Object_Mapping map)
  2048. // ************************************************************************** 
  2049. {  T_PROC("Mapping::local_initialize");
  2050.    TT(agg_H, T_ENTER);
  2051.  
  2052.    sos_Object my_no_object = map;
  2053.  
  2054.    map.set_cardinality (0);
  2055.    map.set_first_object(my_no_object); 
  2056.    map.set_last_object(my_no_object);
  2057.    map.set_ht_entries(0);
  2058.    map.set_global_depth(0);
  2059.    map.set_no_of_pages_offset(NIL);
  2060.    map.set_no_of_pages(0);
  2061.    map.set_ht_offset(NIL);
  2062.  
  2063.    TT(agg_H,T_LEAVE);
  2064. }; // ** Mapping::local_initialize **
  2065.  
  2066. // ************************************************************************** 
  2067. void sos_Object_sos_Object_Mapping::local_finalize
  2068.                                        (sos_Object_sos_Object_Mapping map)
  2069. // ************************************************************************** 
  2070. {  T_PROC("Mapping::local_finalize");
  2071.    TT (agg_H, T_ENTER);
  2072.  
  2073.    destroy_ht(map.get_list_cursor(), map.container(), map.get_ht_entries(), 
  2074.               map.get_global_depth(), map.get_ht_offset());
  2075.  
  2076.    TT (agg_H, T_LEAVE);
  2077. } // ** Mapping::local_finalize **
  2078.  
  2079. // ************************************************************************** 
  2080. sos_Bool sos_Object_sos_Object_Mapping::is_key (sos_Object key)
  2081. // ************************************************************************** 
  2082. {  T_PROC("Mapping::is_key");
  2083.    TT(agg_H, T_ENTER);
  2084.    sos_Object dummy_pred,dummy_succ,dummy_info;
  2085.    sos_Bool result = FALSE;
  2086.    sos_Object my_no_object = self;
  2087.    result = get_entry(self.container(), self.get_list_cursor(),  
  2088.                       self.get_key_based_on_equal(), 
  2089.                       self.get_ht_entries(), self.get_ht_offset(), 
  2090.                       key, FALSE, dummy_info, dummy_pred,dummy_succ);
  2091.    TT(agg_H, T_LEAVE);
  2092.    return result;
  2093. } // ** Mapping::is_key **
  2094.  
  2095.  
  2096. // ************************************************************************** 
  2097. sos_Bool sos_Object_sos_Object_Mapping::is_info (sos_Object info)
  2098. // ************************************************************************** 
  2099. // TRUE, falls info mit insert(*,info) in die Struktur
  2100. // aufgenommen wurde.
  2101. // Vorsicht !! nicht aufrufen !!
  2102. // Die Funktion hat einen Aufwand von o(Anzahl der Eintraege) !!
  2103. {  T_PROC("Mapping::is_info");
  2104.    TT(agg_H,T_ENTER);
  2105.  
  2106.    sos_Container  ct = self.container(); 
  2107.    sos_Bool       list_cursor = self.get_list_cursor();
  2108.    sos_Bool       info_based_on_equal = self.get_info_based_on_equal();
  2109.    ht_entry_t  ht_entry;
  2110.    page_t      page;
  2111.    sos_Object  key;
  2112.  
  2113.       // Durchlaufe die gesamte Hashtabelle
  2114.       // benutze jeden Verweis um die Seite zu durchsuchen,
  2115.       // verwende bei mehrfachen Verweisen nur den ersten
  2116.    sos_Int ht_entries = self.get_ht_entries();
  2117.    sos_Offset ht_offset = self.get_ht_offset();
  2118.    for (sos_Int ht_pos=0;
  2119.         ht_pos < ht_entries; // positiver Abbruch nur in der Schleife
  2120.         ht_pos++)
  2121.    {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
  2122.    
  2123.          // Wie lautet der dieser Seite zugeordnete Hash-Wert ?
  2124.       sos_Int hash_value_part = (LSHIFT(1,ht_entry.local_depth)-1) 
  2125.                                 BITAND ht_pos;
  2126.    
  2127.          // Ist dieser Verweis der erste auf diese Seite ?
  2128.       if (hash_value_part == ht_pos)
  2129.       {     // Ja, 
  2130.          sos_Offset page_offset = ht_entry.page_list_offset;
  2131.          page_header_t page_header = read_page_header(ct, page_offset);
  2132.    
  2133.          sos_Bool found = FALSE;
  2134.          sos_Int pages = page_header.pages;
  2135.      sos_Int entries_on_last_page = page_header.entries_on_last_page;
  2136.      sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
  2137.          for (sos_Int page_no = 1;
  2138.               (page_no<=pages) AND (NOT found);
  2139.               page_no++)
  2140.          {  if (page_no == pages)
  2141.            entries_on_page = entries_on_last_page;
  2142.                 
  2143.             if (entries_on_page > 0)
  2144.                read_page(list_cursor, ct,page_offset, 
  2145.                          entries_on_page, page);
  2146.                
  2147.                // Durchsuche die Seite nach dem Objekt
  2148.             for (sos_Int k=0; 
  2149.                  (NOT found) AND (k<entries_on_page); 
  2150.                  k++)
  2151.             {  key = make_Object(page.entry[k].info);
  2152.                found = agg_same_entity (key,info,info_based_on_equal,EQ_STRONG); 
  2153.         } 
  2154.    
  2155.             if (found) 
  2156.             {  TT(agg_H,T_LEAVE);
  2157.                return TRUE; 
  2158.             } 
  2159.    
  2160.             page_offset = page.page_header.next_page;
  2161.          } 
  2162.       }
  2163.    } 
  2164.  
  2165.    TT(agg_H,T_LEAVE);
  2166.    return FALSE; // Pech ...
  2167. } // ** Mapping::is_info **
  2168.  
  2169. // ************************************************************************** 
  2170. void sos_Object_sos_Object_Mapping::insert(sos_Object Key, sos_Object Entity)
  2171. // ************************************************************************** 
  2172. {  T_PROC("Mapping::insert");
  2173.    TT(agg_H, T_ENTER);
  2174.  
  2175.    sos_Object my_no_object = self;
  2176.       // Das Mappingobjekt selbst wird als Methodenausgabe fuer ein ungueltiges 
  2177.       // Objekt benutzt. Drum kann man NO_OBJECT, aber nicht das
  2178.       // Mappingobjekt einfuegen. Soll es auch auch eingefuegt werden koennen, 
  2179.       // benoetigt man ein eigenes MAPPING_NO_OBJECT.
  2180.    if (Key == self)
  2181.       err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");
  2182.  
  2183.       // fuege das Element in der Listen-Version hinten an die Liste
  2184.       // in der non-Listen Version haben die beiden letzten Parameter
  2185.       // pred und succ keine Wirkung
  2186.    self.insert_in_list(Key, Entity, self.get_last_object(), my_no_object);
  2187.  
  2188.    TT(agg_H,T_LEAVE);   
  2189. } // ** Mapping::insert **
  2190.  
  2191. // ************************************************************************** 
  2192. void sos_Object_sos_Object_Mapping::remove (sos_Object key)
  2193. // ************************************************************************** 
  2194. {  T_PROC("Mapping::remove");
  2195.  
  2196.    sos_Bool found=FALSE;
  2197.  
  2198.    if (self.get_ht_entries() >0)
  2199.    {  sos_Container ct = self.container(); 
  2200.       sos_Int org_hash_value = absolute((self.get_key_based_on_equal())?
  2201.                                         key.hash_value():hash_id(key));
  2202.       sos_Int ht_pos         = org_hash_value MOD self.get_ht_entries();
  2203.       ht_entry_t ht_entry = read_ht_entry(ct,self.get_ht_offset(),ht_pos);
  2204.       found = make_sos_Bool(
  2205.       self.remove_from_page_list (ct, self.get_list_cursor(),
  2206.                               self.get_key_based_on_equal(),
  2207.                               ht_entry.page_list_offset, 
  2208.                                   org_hash_value,key));
  2209.       sos_Object my_no_object = self;
  2210.       if (found)
  2211.       {     // Versuche, die Seitenliste zu verschmelzen
  2212.          if (self.assemble_page(ht_entry.page_list_offset, 
  2213.                                 ht_entry.local_depth, 
  2214.                                 org_hash_value))
  2215.                // versuche, die Hash-Tabelle zu verkleinern
  2216.             self.decrease_hash_table();
  2217.       }
  2218.    } 
  2219.    TT(agg_H,T_LEAVE; TB(found));
  2220. }// ** Mapping::remove **
  2221.  
  2222. // ************************************************************************** 
  2223. sos_Object sos_Object_sos_Object_Mapping::operator[] (sos_Object key)
  2224. // ************************************************************************** 
  2225. {  T_PROC("Mapping::operator[]");
  2226.    TT(agg_H,T_ENTER);
  2227.  
  2228.    sos_Object dummy_pred,dummy_succ,info;
  2229.    sos_Container  ct = self.container();
  2230.    sos_Bool       key_based_on_equal = self.get_key_based_on_equal();
  2231.    sos_Bool       list_cursor = self.get_list_cursor();
  2232.    sos_Object     my_no_object = self;
  2233.    sos_Int        ht_entries = self.get_ht_entries();
  2234.    sos_Offset     ht_offset = self.get_ht_offset();
  2235.  
  2236.    if (NOT get_entry(ct, list_cursor,key_based_on_equal,ht_entries,
  2237.              ht_offset,key,TRUE, info, dummy_pred,dummy_succ))
  2238.       info = NO_OBJECT;
  2239.  
  2240.    TT(agg_H,T_LEAVE);
  2241.    return info;
  2242. } // ** Mapping::operator[] **
  2243.  
  2244. // ************************************************************************** 
  2245. sos_Object sos_Object_sos_Object_Mapping::get_key(sos_Cursor c)
  2246. // ************************************************************************** 
  2247. {  T_PROC("Mapping::get_key(sos_Cursor)");
  2248.    TT(agg_H, T_ENTER);
  2249.  
  2250.    err_assert (c.defined_for (self), "Mapping:get_key");
  2251.    err_assert (self.is_valid(c), "Mapping:get_key");
  2252.  
  2253.    sos_Map_node mn = sos_Map_node::make (c.get_current());
  2254.    sos_Object   o  = mn.get_key_val();
  2255.  
  2256.    TT(agg_H,T_LEAVE);
  2257.    return o;
  2258. } // ** Mapping::get_key **
  2259.  
  2260. // ************************************************************************** 
  2261. sos_Object sos_Object_sos_Object_Mapping::get_info(sos_Cursor c)
  2262. // ************************************************************************** 
  2263. {  T_PROC("Mapping::get_info(sos_Cursor)");
  2264.    TT(agg_H, T_ENTER);
  2265.  
  2266.    err_assert (c.defined_for (self), "Mapping:get_info");
  2267.    err_assert(self.is_valid(c),"Mapping:get_info");
  2268.  
  2269.    sos_Object my_no_object = self;
  2270.    sos_Object dummy_pred,
  2271.           dummy_succ;
  2272.  
  2273.    sos_Object key = sos_Map_node::make (c.get_current()).get_key_val();
  2274.    sos_Object info;
  2275.    sos_Bool found = get_entry(self.container(), self.get_list_cursor(),
  2276.                               self.get_key_based_on_equal(),
  2277.                               self.get_ht_entries(), self.get_ht_offset(), 
  2278.                               key,TRUE, info,dummy_pred,dummy_succ);
  2279.       // Beliebter Benutzerfehler: Ein Prozess erzeugt
  2280.       // einen Eintrag mit einem Key im TEMP_CONTAINER, das
  2281.       // Programm beendet, ein anderer Prozess versucht darueber
  2282.       // zu itterieren. Trotz das im Key Bockmist steht, kann er
  2283.       // noch mit get_key geliefert werden. Wenn jedoch der passende Eintrag 
  2284.       // dazu gesucht wird, wird der Hashwert vom Key gebraucht. In diesem
  2285.       // stehen wilde Sachen, der Eintrag wird (vermutlich) nicht gefunden.
  2286.    if (NOT found)
  2287.       err_raise(err_USE,"Entry didn't exists anymore","Mapping::get_info");
  2288.  
  2289.    TT(agg_H, T_LEAVE);
  2290.    return info;
  2291. } // ** Mapping::get_info **
  2292.  
  2293. // ************************************************************************** 
  2294. void sos_Object_sos_Object_Mapping::set_info(sos_Cursor c, sos_Object o)
  2295. // ************************************************************************** 
  2296. {  T_PROC ("Mapping::set_info");
  2297.    TT (agg_H, T_ENTER);
  2298.  
  2299.    err_assert ((c.defined_for (self)), "Mapping:set_info");
  2300.    self.insert (sos_Map_node::make (c.get_current()).get_key_val(), o);
  2301.  
  2302.    TT (agg_H, T_LEAVE);
  2303. } // ** Mapping::set_info **
  2304.  
  2305. // ************************************************************************** 
  2306. void sos_Object_sos_Object_Mapping::move_cursor(sos_Cursor c, sos_Object key)
  2307. // ************************************************************************** 
  2308. // sets the cursor c to the key object in the mapping that corresponds
  2309. // to the given key
  2310. {  T_PROC ("Mapping::move_cursor");
  2311.    TT( agg_H, T_ENTER);
  2312.  
  2313.    err_assert (c.defined_for (self), "Mapping:move_cursor");
  2314.    err_assert (self.is_key(key), "Mapping:move_cursor");
  2315.  
  2316.    sos_Object dummy_pred, dummy_succ, dummy_info;
  2317.    sos_Bool found = get_entry(self.container(), self.get_list_cursor(),
  2318.                               self.get_key_based_on_equal(),
  2319.                               self.get_ht_entries(),self.get_ht_offset(),
  2320.                               key,FALSE, dummy_info, dummy_pred,dummy_succ);
  2321.    err_assert (found, "Mapping:move_cursor");
  2322.    sos_Map_node::make (c.get_current()).set_key_val(key); 
  2323.  
  2324.    TT(agg_H, T_LEAVE);
  2325. } // ** Mapping::move_cursor **
  2326.  
  2327. // ************************************************************************** 
  2328. void sos_Object_sos_Object_Mapping::insert_before (sos_Cursor c,
  2329.                                                    sos_Object Key,
  2330.                                                    sos_Object Entity)
  2331. // ************************************************************************** 
  2332. {  T_PROC("Mapping::insert_before");
  2333.    TT(agg_H, T_ENTER);
  2334.  
  2335.    err_assert (self.get_list_cursor(), "Mapping:insert_before");
  2336.    err_assert (c.defined_for (self), "Mapping:insert_before");
  2337.    err_assert (self.is_valid(c), "Mapping:insert_before");
  2338.  
  2339.    if (Key == self)
  2340.       err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");
  2341.    sos_Map_node mn = sos_Map_node::make (c.get_current());
  2342.  
  2343.    sos_Object dummy_info,pred,dummy_succ;
  2344.    sos_Object key = mn.get_key_val();
  2345.    get_entry(self.container(), self.get_list_cursor(), 
  2346.              self.get_key_based_on_equal(),
  2347.              self.get_ht_entries(),self.get_ht_offset(),
  2348.              key,FALSE, dummy_info, pred,dummy_succ);
  2349.    self.insert_in_list(Key, Entity, pred, mn.get_key_val());
  2350.  
  2351.    TT(agg_H, T_LEAVE);
  2352. } // ** Mapping::insert_before **
  2353.  
  2354. // ************************************************************************** 
  2355. void sos_Object_sos_Object_Mapping::insert_after (sos_Cursor c,
  2356.                                                   sos_Object Key,
  2357.                                                   sos_Object Entity)
  2358. // ************************************************************************** 
  2359. {  T_PROC("Mapping::insert_after");
  2360.    TT(agg_H, T_ENTER);
  2361.  
  2362.    err_assert (self.get_list_cursor(), "Mapping:insert_after");
  2363.    err_assert (c.defined_for (self), "Mapping:insert_after");
  2364.    err_assert (self.is_valid(c), "Mapping:insert_after");
  2365.  
  2366.    if (Key == self)
  2367.       err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");
  2368.  
  2369.    sos_Map_node mn = sos_Map_node::make (c.get_current());
  2370.  
  2371.    sos_Object dummy_info,dummy_pred,succ;
  2372.    sos_Object key = mn.get_key_val();
  2373.    get_entry(self.container(), self.get_list_cursor(), 
  2374.              self.get_key_based_on_equal(),
  2375.              self.get_ht_entries(),self.get_ht_offset(),
  2376.              key,FALSE,dummy_info,dummy_pred,succ);
  2377.    self.insert_in_list(Key, Entity, mn.get_key_val(), succ);
  2378.  
  2379.    TT(agg_H, T_LEAVE);
  2380. } // ** Mapping::insert_after **
  2381.  
  2382. // ************************************************************************** 
  2383. void sos_Object_sos_Object_Mapping::local_assign
  2384.                                        (sos_Object_sos_Object_Mapping x,
  2385.                                         sos_Object                    o)
  2386. // ************************************************************************** 
  2387. {  T_PROC("Mapping::local_assign");
  2388.  
  2389.    sos_Object_sos_Object_Mapping y = sos_Object_sos_Object_Mapping::make (o);
  2390.    sos_Container y_ct = y.container();
  2391.    sos_Container x_ct = x.container();
  2392.    sos_Bool x_list_cursor = x.get_list_cursor();
  2393.    
  2394.    err_assert ((y.get_list_cursor() == x_list_cursor),
  2395.                "Mapping::local_assign");
  2396.  
  2397.    destroy_ht(x_list_cursor, x_ct, x.get_ht_entries(),
  2398.               x.get_global_depth(), x.get_ht_offset());
  2399.  
  2400.    sos_Bool key_based_on_equal = y.get_key_based_on_equal();
  2401.    sos_Bool info_based_on_equal= y.get_info_based_on_equal();
  2402.    sos_Int cardinality         = y.get_cardinality();
  2403.    sos_Int no_of_pages         = y.get_no_of_pages();
  2404.    sos_Int no_of_page_lists    = y.get_no_of_page_lists();
  2405.    sos_Int global_depth        = y.get_global_depth();
  2406.    sos_Int ht_entries          = y.get_ht_entries();
  2407.    sos_Int no_of_pages_offset  = y.get_no_of_pages_offset();
  2408.  
  2409.    x.set_key_based_on_equal(key_based_on_equal);
  2410.    x.set_info_based_on_equal(info_based_on_equal);
  2411.    x.set_cardinality(cardinality);
  2412.    x.set_no_of_pages(no_of_pages);
  2413.    x.set_no_of_page_lists(no_of_page_lists);
  2414.    x.set_global_depth(global_depth);
  2415.    x.set_ht_entries(ht_entries);
  2416.    x.set_first_object(y.get_first_object());
  2417.    x.set_last_object(y.get_last_object());
  2418.  
  2419.  
  2420.    if (cardinality != 0)
  2421.    {    // kopiere das Feld fuer no_of_pages rueber
  2422.       sos_Offset new_no_of_pages_offset = x_ct.allocate(NO_OF_PAGES_ARRAY_SIZE);
  2423.       x.set_no_of_pages_offset(new_no_of_pages_offset);
  2424.       sos_Char mem [NO_OF_PAGES_ARRAY_SIZE];
  2425.       y_ct.read(no_of_pages_offset, NO_OF_PAGES_ARRAY_SIZE, &mem);
  2426.       x_ct.write(new_no_of_pages_offset, NO_OF_PAGES_ARRAY_SIZE, &mem);
  2427.   
  2428.          // erzeuge die Hashtabelle
  2429.       x.set_ht_offset(x_ct.allocate(y.get_ht_entries() *HT_ENTRY_SIZE));
  2430.          // Laufe die erste HT durch und kopiere die Seiten
  2431.       sos_Offset old_ht_offset = y.get_ht_offset();
  2432.       sos_Offset new_ht_offset = x.get_ht_offset();
  2433.       for (sos_Int ht_pos = 0;ht_pos<y.get_ht_entries();ht_pos++)
  2434.       {  ht_entry_t ht_entry = read_ht_entry(y_ct,old_ht_offset,ht_pos);
  2435.    
  2436.             // Ist es der erste Zeiger auf die Seitenliste ?
  2437.          sos_Int local_depth = ht_entry.local_depth;
  2438.          sos_Int first_link = FIRST_LINK(ht_pos, local_depth);
  2439.          if (first_link == ht_pos)
  2440.          {     // erster Verweis, kopiere die Seitenliste
  2441.             sos_Offset old_page_offset = ht_entry.page_list_offset;
  2442.             page_header_t  old_first_page_header = 
  2443.                 read_page_header(y_ct, ht_entry.page_list_offset);
  2444.    
  2445.             sos_Offset pred_page_offset=0;
  2446.    
  2447.             for(sos_Int page_no=1;page_no<=old_first_page_header.pages;page_no++)
  2448.             {  sos_Offset new_page_offset = 
  2449.           x_ct.allocate(PAGE_SIZE(x_list_cursor));
  2450.                if (page_no == 1)
  2451.                   ht_entry.page_list_offset = new_page_offset;
  2452.                else
  2453.                {  page_header_t tmp_page_header = old_first_page_header;
  2454.                   tmp_page_header.next_page = new_page_offset;
  2455.                   // schreibe den Seitenverweis in den Vorgaenger
  2456.                   write_page_header(x_ct,pred_page_offset, tmp_page_header);
  2457.                }
  2458.    
  2459.                page_t tmp_page;
  2460.                sos_Int entries = (page_no < old_first_page_header.pages)?
  2461.                                  MAX_PAGE_ENTRIES(x_list_cursor):
  2462.                                  old_first_page_header.entries_on_last_page;
  2463.  
  2464.                   // kopiere die Seite
  2465.                read_page(x_list_cursor,y_ct,old_page_offset,entries,tmp_page);
  2466.                write_page(x_list_cursor, x_ct,new_page_offset,
  2467.                           MAX_PAGE_ENTRIES(x_list_cursor), tmp_page);
  2468.                pred_page_offset = new_page_offset;
  2469.    
  2470.                   // lese den Seitenkopf der Seite, um 
  2471.           // Nachfolgerseite rauszufinden
  2472.                page_header_t old_page_header = 
  2473.                   read_page_header(y_ct,old_page_offset);
  2474.                
  2475.                old_page_offset = old_page_header.next_page;
  2476.             } // kopiere alle Seiten
  2477.    
  2478.                // schreibe den HT-Eintrag in alle Verweise der HT
  2479.             sos_Int no_of_links = LSHIFT(1,global_depth-local_depth);
  2480.             for (sos_Int k=0;k<no_of_links;k++)
  2481.             {  sos_Int x = LSHIFT(k,local_depth);
  2482.                sos_Int other_link = x BITOR ht_pos;
  2483.                write_ht_entry(x_ct,new_ht_offset,other_link,ht_entry);
  2484.             } // schreibe alle HT-Eintraege pro Seite
  2485.          } 
  2486.       } 
  2487.       if (x_list_cursor)
  2488.       {  sos_Object my_no_object = x;
  2489.          x.write_succ_pred
  2490.             (x_ct, key_based_on_equal, x_list_cursor, 
  2491.              x.get_first_object(), FALSE, my_no_object);
  2492.          x.write_succ_pred
  2493.             (x_ct, key_based_on_equal, x_list_cursor,  
  2494.              x.get_last_object(), TRUE, my_no_object);
  2495.       }
  2496.    }
  2497.    else
  2498.    {     // Kein Element drin, erzeuge nichts, initialisere wie in local_init
  2499.       sos_Object my_no_object = x;
  2500.       x.set_first_object(my_no_object);
  2501.       x.set_last_object(my_no_object);
  2502.       x.set_ht_offset(NIL);
  2503.       x.set_ht_entries(0);
  2504.       x.set_no_of_pages_offset(NIL);
  2505.    }
  2506.  
  2507.    TT(agg_H,T_LEAVE); 
  2508. } // ** Mapping::local_assign **
  2509.  
  2510. // ************************************************************************** 
  2511. sos_Bool sos_Object_sos_Object_Mapping::local_equal
  2512.                                        (sos_Object_sos_Object_Mapping x,
  2513.                                         sos_Object                    o,
  2514.                                         sos_Eq_kind                   eq_kind) 
  2515. // ************************************************************************** 
  2516. {  sos_Bool result;
  2517.  
  2518.    if ((eq_kind EQ EQ_STRONG AND NOT o.has_type(x.type())) OR
  2519.        (eq_kind EQ EQ_WEAK   AND NOT o.isa     (x.type())))
  2520.       result = FALSE;
  2521.    else
  2522.    {  sos_Object_sos_Object_Mapping y = 
  2523.          sos_Object_sos_Object_Mapping::make (o);
  2524.       if (y.get_cardinality() != x.get_cardinality())
  2525.          result = FALSE; 
  2526.       else
  2527.       {  sos_Bool info_based_on_equal = x.get_info_based_on_equal();
  2528.          agg_iterate_association (x, sos_Object key, sos_Object info)
  2529.          {  if (NOT agg_same_entity (y[key],info,info_based_on_equal,eq_kind))
  2530.             {  result = FALSE;
  2531.                break;
  2532.             }
  2533.          } 
  2534.          agg_iterate_association_end (x, key, info);
  2535.       }
  2536.    }
  2537.  
  2538.    return result;
  2539. } // ** Mapping::local_equal **
  2540.  
  2541. // ************************************************************************** 
  2542. sos_Int sos_Object_sos_Object_Mapping::local_hash_value
  2543.                                        (sos_Object_sos_Object_Mapping m)
  2544. // ************************************************************************** 
  2545. // Ansich muesste der augenblickliche Hashwert gespeichert werden, und bei 
  2546. // jedem eingefuegten Element mit einer reversiblen Operation verknuepft 
  2547. // werden. Bei jedem remove, muss diese reversible Operation aufgerufen 
  2548. // werden. Zu viel Aufwand, drum bisher noch nicht implementiert.
  2549. {  return m.card();
  2550. } // ** Mapping::local_hash_value **
  2551.  
  2552. // ************************************************************************** 
  2553. sos_Int sos_Object_sos_Object_Mapping::size()
  2554. // ************************************************************************** 
  2555. {  sos_Int o_size = sos_Object::size();
  2556.    sos_Int ht_size = self.get_ht_entries() * HT_ENTRY_SIZE;
  2557.    sos_Int nop_size = (ht_size>0)?NO_OF_PAGES_ARRAY_SIZE:0;
  2558.    sos_Int pg_size = self.get_no_of_pages()*PAGE_SIZE(self.get_list_cursor());
  2559.    return o_size +
  2560.           self.container().rounded (ht_size) +
  2561.           self.container().rounded (pg_size) +
  2562.           self.container().rounded (nop_size);
  2563. } // ** Mapping::size **
  2564.  
  2565. // **************************************************************************
  2566. sos_Bool sos_Object_sos_Object_Mapping::is_role1 (sos_Object key)
  2567. // **************************************************************************
  2568. {  return self.is_key (key);
  2569. } // ** Mapping::is_role1 **
  2570.  
  2571. // **************************************************************************
  2572. sos_Bool sos_Object_sos_Object_Mapping::is_role2 (sos_Object info)
  2573. // **************************************************************************
  2574. {  return self.is_info (info);
  2575. } // ** Mapping::is_role2 **
  2576.  
  2577. // **************************************************************************
  2578. sos_Object sos_Object_sos_Object_Mapping::get_role1 (sos_Cursor c)
  2579. // **************************************************************************
  2580. {  return self.get_key (c);
  2581. } // ** Mapping::get_role1 **
  2582.  
  2583. // **************************************************************************
  2584. sos_Object sos_Object_sos_Object_Mapping::get_role2 (sos_Cursor c)
  2585. // **************************************************************************
  2586. {  return self.get_info (c);
  2587. } // ** Mapping::get_role2 **
  2588.  
  2589. // ************************************************************************** 
  2590. void sos_Object_sos_Object_Mapping::remove_at(sos_Cursor c)
  2591. // ************************************************************************** 
  2592. {  T_PROC("Mapping::remove_at");
  2593.    TT(agg_H, T_ENTER);
  2594.  
  2595.    err_assert (c.defined_for (self), "Mapping:remove_at");
  2596.    err_assert (self.is_valid(c), "Mapping:remove_at");
  2597.  
  2598.    sos_Object key = self.get_key(c);
  2599.  
  2600.    if (self.get_list_cursor())
  2601.       self.to_succ(c);
  2602.    else
  2603.    {     // Setze Cursor auf my_no_object => is_valid == FALSE
  2604.       sos_Object my_no_object = self;
  2605.       sos_Map_node mn = sos_Map_node::make (c.get_current());
  2606.       mn.set_key_val(my_no_object);
  2607.    }
  2608.  
  2609.    self.remove(key);
  2610.  
  2611.    TT(agg_H, T_LEAVE);
  2612. } // ** Mapping::remove_at **
  2613.  
  2614. // ************************************************************************** 
  2615. void sos_Object_sos_Object_Mapping::clear()
  2616. // ************************************************************************** 
  2617. {  T_PROC("Mapping::clear");
  2618.    TT(agg_H, T_ENTER);
  2619.    
  2620.    sos_Container ct = self.container();
  2621.    sos_Int ht_entries = self.get_ht_entries();
  2622.    if (ht_entries >0)
  2623.       destroy_ht(self.get_list_cursor(), ct, ht_entries,
  2624.                  self.get_global_depth(), self.get_ht_offset());
  2625.  
  2626.    sos_Object my_no_object = self;
  2627.    self.set_first_object(my_no_object);
  2628.    self.set_last_object(my_no_object);
  2629.    self.set_cardinality (0);
  2630.    self.set_ht_entries(0);
  2631.    self.set_global_depth(0);
  2632.    self.set_no_of_pages_offset(NIL);
  2633.    self.set_no_of_pages(0);
  2634.    self.set_ht_offset(NIL);
  2635.  
  2636.    TT(agg_H, T_LEAVE);
  2637. } // ** Mapping::clear **
  2638.  
  2639. // **************************************************************************
  2640. sos_Int sos_Object_sos_Object_Mapping::card ()
  2641. // **************************************************************************
  2642. {  T_PROC ("Mapping::card");
  2643.    TT (agg_H, T_ENTER);
  2644.  
  2645.    sos_Int crd = self.get_cardinality();
  2646.  
  2647.    TT (agg_H, T_LEAVE);
  2648.    return crd;
  2649. } // ** Mapping::card **
  2650.  
  2651. // ************************************************************************** 
  2652. sos_Cursor sos_Object_sos_Object_Mapping::open_cursor(sos_Container Cursor_ct)
  2653. // ************************************************************************** 
  2654. {  T_PROC ("Mapping::open_cursor");
  2655.    TT( agg_H, T_ENTER);
  2656.  
  2657.    sos_Cursor c = sos_Cursor::create(Cursor_ct, self);
  2658.    sos_Map_node mn = sos_Map_node::create(Cursor_ct);
  2659.    c.set_current(mn);
  2660.  
  2661.    self.to_first(c);
  2662.  
  2663.    TT(agg_H, T_LEAVE);
  2664.    return c;
  2665. } // ** Mapping::open_cursor **
  2666.  
  2667. // ************************************************************************** 
  2668. void sos_Object_sos_Object_Mapping::close_cursor(sos_Cursor c)
  2669. // ************************************************************************** 
  2670. {  err_assert ((c.defined_for (self)), "Mapping:close_cursor");
  2671.    c.get_current().destroy(); 
  2672.    c.destroy(); 
  2673. } // ** Mapping::close_cursor **
  2674.  
  2675. // ************************************************************************** 
  2676. sos_Cursor sos_Object_sos_Object_Mapping::duplicate(sos_Cursor c)
  2677. // ************************************************************************** 
  2678. {  err_assert ((c.defined_for (self)), "Mapping:duplicate");
  2679.    sos_Container Cursor_ct = c.container();
  2680.  
  2681.    sos_Cursor dup_c = sos_Cursor::create(Cursor_ct, self);
  2682.    sos_Map_node dup_mn = sos_Map_node::create(Cursor_ct);
  2683.  
  2684.    dup_c.set_current (dup_mn);
  2685.    dup_mn.set_key_val (sos_Map_node::make (c.get_current()).get_key_val());
  2686.  
  2687.    return dup_c;
  2688. } // ** Mapping::duplicate **
  2689.  
  2690. // **************************************************************************
  2691. sos_Bool sos_Object_sos_Object_Mapping::is_valid (sos_Cursor c)
  2692. // **************************************************************************
  2693. {  sos_Map_node mn           = sos_Map_node::make (c.get_current());
  2694.    sos_Object   my_no_object = self;
  2695.    sos_Bool     valid        = (mn.get_key_val() != my_no_object);
  2696.  
  2697.    return valid;
  2698. } // ** is_valid **
  2699.  
  2700. // ************************************************************************** 
  2701. sos_Bool sos_Object_sos_Object_Mapping::to_first(sos_Cursor c)
  2702. // ************************************************************************** 
  2703. {  err_assert ((c.defined_for (self)), "Mapping:to_first");
  2704.    sos_Container Cursor_ct = c.container();
  2705.    sos_Map_node  current = sos_Map_node::make (c.get_current());
  2706.    sos_Object    my_no_object = self;
  2707.    sos_Object    first;
  2708.  
  2709.    if (self.get_cardinality() > 0)
  2710.    {  if (NOT (self.get_list_cursor()))
  2711.          first = read_first_object(self.container(),self.get_ht_offset(),
  2712.                                    self.get_cardinality(),my_no_object);
  2713.       else
  2714.          first = self.get_first_object();
  2715.    }
  2716.    else
  2717.       first = my_no_object;
  2718.    
  2719.    current.set_key_val(first);
  2720.  
  2721.    return self.is_valid(c);
  2722. } // ** Mapping::to_first **
  2723.  
  2724. // ************************************************************************** 
  2725. sos_Bool sos_Object_sos_Object_Mapping::to_last(sos_Cursor c)
  2726. // ************************************************************************** 
  2727. {  err_assert ((c.defined_for (self)), "Mapping:to_last");
  2728.    sos_Map_node  current      = sos_Map_node::make (c.get_current());
  2729.    sos_Container Cursor_ct    = c.container();
  2730.    sos_Object    my_no_object = self;
  2731.    sos_Object    last;
  2732.  
  2733.    if (self.get_cardinality() > 0)
  2734.    {  if (NOT (self.get_list_cursor()))
  2735.          last = read_last_object
  2736.                    (self.container(),
  2737.                     self.get_ht_offset(),self.get_cardinality(),
  2738.                     my_no_object,self.get_ht_entries());
  2739.       else
  2740.          last = self.get_last_object();
  2741.    }      
  2742.    else
  2743.       last = my_no_object;
  2744.  
  2745.    current.set_key_val(last);
  2746.  
  2747.    return self.is_valid(c);
  2748. } // ** Mapping::to_last **
  2749.  
  2750. // ************************************************************************** 
  2751. sos_Bool sos_Object_sos_Object_Mapping::to_succ(sos_Cursor c, Index i) 
  2752. // ************************************************************************** 
  2753. {  err_assert (c.defined_for (self), "Mapping:to_succ");
  2754.    err_assert (self.is_valid(c), "Mapping:to_succ");
  2755.  
  2756.    sos_Map_node mn = sos_Map_node::make (c.get_current());
  2757.    sos_Object   o  = self.search_succ_pred (mn.get_key_val(),i);
  2758.  
  2759.    mn.set_key_val (o); 
  2760.  
  2761.    return self.is_valid (c);
  2762. } // ** Mapping::to_succ **
  2763.  
  2764. // ************************************************************************** 
  2765. sos_Bool sos_Object_sos_Object_Mapping::to_pred(sos_Cursor c, Index i)
  2766. // ************************************************************************** 
  2767. {  return self.to_succ(c,-i); 
  2768. } // ** Mapping::to_pred **
  2769.